2020-05-02比赛总结
starseven
2020-05-08 20:21:52
实际上除了第三题带有难度（对于没有数据结构刷题量的人来说，剩下的两道题可以说是简单题）
### T1
[题面](https://www.luogu.com.cn/problem/P5451)
现在的题面都很长，可是我们要仔细分析。在考场上一定要想出题人的意图，我们看看题目:
$$ c_1 = m^{e_1}mod N $$
$$ c_2 =m^{e_2}mod N $$
考场上仔细想一想就知道，出题人难道是白痴吗，告诉你
**如果找到可以快速分解大整数的方法，密码安全性就收到威胁**
然后就可以在考场上叫你打一个很多人听都没听过的算法？！QwQ
所以我在考场上思考了一会儿，就注意到上面的东西（我再展示一次）
$$ c_1 = m^{e_1}\mod N $$
$$ c_2 =m^{e_2}\mod N $$
很显然，出题人给了你两个等式，我们的切入点就应该在两个等式的关系上入口。
我们再看题目：
### 设两个用户的公钥分别为e1 和e2，且两者互质。 ##
所以根据我们要（~~四声~~）求的m，我们就会联想到指数，m的指数为1，这个时候学过欧几里得算法的人们就会警惕，诶，我们在学扩展欧几里得的时候不是见到过这个等式吗：
$$ e_1\times x +e_2\times y=gcd(e_1,e_2) $$
由于我们校内检测是刚学了数论考的，所以我很容易联想到，但这也是AC这道题的基本素养。
因为两者互质，所以我们明显可以先将两个等式的指数变为只相差一的式子，然后相除（就是逆元）就可以AC了。
对于一些数论还不熟悉的同学（我在很长时间内也是），我现在讲一下为什么可以转化。
自己想：
$$ x\; mod\;N=g$$
那么
$$ x^{n}\;mod\;N=g^{n} $$
这是其一；
然后就是上方展示的扩展欧几里得的公式了
代码如下
```cpp
#include<cstdio>
#include<iostream>
#define ll long long
#define Starseven main
using namespace std;
ll read();
void write(ll);
ll c1,c2,e1,e2,N;
ll Multi(ll a,ll b,ll p){
ll re=0;
while(b){
if(b&1) re=(re+a)%p;
b>>=1;
a=(a*2)%p;
}
return re%p;
}
ll Get_exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;return a;
}
ll temp=Get_exgcd(b,a%b,x,y);
ll t=x;x=y;y=t-a/b*y;
return temp;
}
ll Power(ll a,ll b,ll p){
ll re=1;
while(b){
if(b&1) re=Multi(re,a,p);
b>>=1;
a=Multi(a,a,p);
}
return re%p;
}
int Starseven(void){
int t=read();
while(t--){
c1=read(),c2=read(),e1=read(),e2=read(),N=read();
//cout<<c1<<" "<<c2<<" "<<e1<<" "<<e2<<" "<<N<<endl;
ll x,y;
ll judge=Get_exgcd(e1,e2,x,y);
while(x<0){
x+=e2,y-=e1;
}
ll a=Power(c1,x,N),b=Power(c2,-y,N);
ll f,g;
ll hh=Get_exgcd(b,N,f,g);
ll ans=Multi(f,a,N);
ans=(ans+N)%N;
write(ans);
puts("");
}
return 0;
}
ll read(){
char ch=getchar();
ll re=0,op=1;
while(ch<'0'||ch>'9'){
if(ch=='-') op=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
re=re*10+ch-'0';
ch=getchar();
}
return re*op;
}
void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
```
### T2
[题面](https://www.luogu.com.cn/problem/P4251)
我们先看一道例题：
[P1129 [ZJOI2007]矩阵游戏](https://www.luogu.com.cn/problem/P1129)
这道例题是二分图的入门题当中的难题（对我来说），当时我在机房和以为同学讨论了一晚上才懂，哈哈哈。
#### 游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。
我们一看，对角线均为黑色，好吧，我讲不清楚，但是你看了我讲的之后可以看看讲懂我的题解。
我们看得出来无论怎么交换都不会影响行和列的黑子有矛盾，就是重合，所有就将每行和每列连边，然后跑二分图匹配（说实在话，我觉得例题对于二分图的思维难度都比这道题高……）
现在给大家看看讲懂我的[博客](https://www.luogu.com.cn/blog/sswcdak/solution-p1129)
这个是[俾斯麦](https://www.luogu.com.cn/user/119937)（洛谷名）的，如有侵权，作者将及时删除。
现在我们看这道题
#### 其中任意两个数都不能在同一行或者同一列。
这就是裸题了啊！我们就直接每一次每行和每列连边，当然，因为我们要求答案，发现不能直接求出，所以考虑二分答案，因此我们连的边必须是小于等于我们二分出来的东西，因此我们就每次清零一次，就可以了。
现在贴代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int MAXN = 255;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
int n,m,k,w[MAXN*MAXN];
int a[MAXN][MAXN],tot,ans,now;
int head[MAXN*MAXN],cnt;
int vis[MAXN*MAXN],num,match[MAXN*MAXN];
int to[MAXN*MAXN<<1],nxt[MAXN*MAXN<<1];
inline void add(int bg,int ed){
to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}
bool dfs(int x){
for(register int i=head[x];i;i=nxt[i]){
int u=to[i];
if(vis[u]!=num){
vis[u]=num;
if(!match[u] || dfs(match[u])){
match[u]=x;
return true;
}
}
}
return false;
}
inline bool check(int Mid){
memset(head,0,sizeof(head));
memset(match,0,sizeof(match));
ans=cnt=0;
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++)
if(a[i][j]<=Mid) add(i,j);
for(register int i=1;i<=n;i++){
num++;
if(dfs(i)) ans++;
}
if(ans>n-k) return true;
return false;
}
int main(){
n=rd(),m=rd(),k=rd();
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++){
a[i][j]=rd();
w[++tot]=a[i][j];
}
sort(w+1,w+1+tot);
int l=1,r=tot,mid;
while(l<=r){
mid=l+r>>1;
if(check(w[mid])) {
now=mid;
r=mid-1;
}
else l=mid+1;
}cout<<w[now]<<endl;
return 0;
}
```
### T3
[题面](https://www.luogu.com.cn/problem/P5226)
这道题就是我认为需要数据结构（起码是线段树）的刷题量，当然，比我强的人除外。
对于所有的环，目前我见过最好的做法就是断环成链，然后倍长，因为这样做了以后对于某一点x,我们伸长一个换的距离恰好便是以这个点为起点的环，这样的话对于环的“最长距离”便有了很好的交代（因为对于环来说，最短距离得看是从左边走还是右边走，而这如果断环成链的话，就简化成了这个点的左边&这个点的右边）
$$ b[0]=a[0] $$
$$ b[i]=(a[i]+a[i-1])\;mod\;10 $$
$$ b[i]=(a[i] \times a[i-1])\;mod\;10 $$
这样的话我们就会发现，每次修改a[i]和运算符号，最多有四个值改变
### 为什么最多是四个呢
按道理来讲是显然的，但是担心有些同学题做昏了，我现在说一下：
我们之前已经倍长了一次，对于不在第一个和最后一个的点，假设他是a[i],这个时候a[i]和符号改变，那根据上面的公式，b[i]和b[i+1]一定会改变（注意，我们在前面说了的：i>1&&i<n），然后我们是倍长的，也就是说1~n和n+1~n+n+1一定是一一对应的，那我们也一定要改对应的部分，这样的话就变成了改四个点，四个点有点少，所以我们只需要做到单点修改
写到这里读者就应该明白了，我们需要用一个线段树，可是我们不是由线段树想到拆环，而是由拆环想到线段树。所以笔者片面认为，思想比算法更重要。
我们现在就可以看出题目的大概做法了，我不觉得其他有什么好讲了的。
被打脸，我在重新编辑的时候发现这个 **二分** 是有必要讲一下的：
对于查询的时候，我们应该注意以下几点
- 特判
----
特判有两点。
1. 对于要输出-1的，一定要特判
这个时候就相当于整个环都没有一个零，那么直接线段树查询就可以了。
-----
2. 对于输出0的，一定要特判
什么情况输出0，当然就是本身为0，并且其他地方没有0.
如果不特判的话，可能就会死循环（虽然我的二分重来没写对过）
----
- 二分
二分注意边界条件和基本常识就可以了
我们由于要找最远的0区间，所以边界r=n/2
-----
现在贴代码：
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define ls (p<<1)
#define rs (p<<1|1)
#define maxn 100005
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int n,m;
int a[maxn<<1],b[maxn<<1];
char c[maxn<<1];
struct node
{
int l,r,pre,suf,str,cnt;
inline void init(int val)
{
str=0;
if(val) cnt=pre=suf=1;
else cnt=pre=suf=0;
}
}tree[maxn<<4];
node operator + (const node &a,const node &b)
{
node c;
c.l=a.l;c.r=b.r;
c.str=a.str+b.str;
c.cnt=a.cnt+b.cnt;
c.pre=a.pre;
c.suf=b.suf;
if(a.cnt&&b.cnt&&(!a.suf||!b.pre)) ++c.str;
return c;
}
inline void build(int p,int l,int r)
{
tree[p].l=l;tree[p].r=r;
if(l==r) return;
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
inline void update(int p,int pos,int x)
{
int l=tree[p].l,r=tree[p].r;
if(l==r) {tree[p].init(x);return;}
int mid=(l+r)>>1;
if(pos<=mid) update(ls,pos,x);
else update(rs,pos,x);
tree[p]=tree[ls]+tree[rs];
}
inline node query(int p,int L,int R)
{
int l=tree[p].l,r=tree[p].r;
if(L<=l&&r<=R) return tree[p];
int mid=(l+r)>>1;
if(R<=mid) return query(ls,L,R);
else if(L>mid) return query(rs,L,R);
else return query(ls,L,R)+query(rs,L,R);
}
inline int calc(int i)
{
return c[i]=='*'?(a[i]*a[i-1])%10:(a[i]+a[i-1])%10;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
{
a[i]=read();scanf(" %c",&c[i]);
a[n+i]=a[i];
c[n+i]=c[i];
}
build(1,1,n<<1);
for(int i=2;i<=(n<<1);i++)
update(1,i,calc(i));
while(m--)
{
int opt=read(),pos=read()+1;
if(opt==1)
{
a[pos]=read();scanf(" %c",&c[pos]);
a[pos+n]=a[pos];
c[pos+n]=c[pos];
if(pos>1) update(1,pos,calc(pos));
update(1,pos+1,calc(pos+1));
update(1,n+pos,calc(n+pos));
if(pos<n) update(1,n+pos+1,calc(n+pos+1));
}
else
{
if(!a[pos]&&query(1,pos+1,pos+n-1).str==0){puts("0");continue;}
update(1,pos,a[pos]);
update(1,pos+n,a[pos]);
int l=0,r=n>>1,ans=-2;
while(l<=r)
{
int mid=(l+r)>>1;
if(query(1,pos+mid,n+pos-mid).str) ans=mid,l=mid+1;
else r=mid-1;
}
++ans;
printf("%d\n",ans);
if(pos>1) update(1,pos,calc(pos));
update(1,pos+n,calc(pos+n));
}
}
return 0;
}
```