pick一波出题人：
剩下的没找到链接55
A. UpMing的迷宫
代码：
int n,m,ans[222222],a[2222][2222],vis[2222][2222]; int dx[4] = {1,0,-1,0},cnt,num; int dy[4] = {0,1,0,-1}; int ok (int x,int y) { if(vis[x][y]||x<1||x>n||y<1||y>n) return 0; return 1; } void dfs(int x,int y) { vis[x][y] =cnt ; num++; for(int i=0 ; i<4 ; i++) { int x1 = x+dx[i]; int y1 = y+dy[i]; if(ok(x1,y1)==0) continue; if(a[x][y]==a[x1][y1]) continue; dfs(x1,y1); } } int main() { n=read(),m=read(); rep(i,1,n) rep(j,1,n) scanf("%1d",&a[i][j]); rep(i,1,n) rep(j,1,n) if(vis[i][j]==0) ++cnt,dfs(i,j),ans[cnt]=num,num=0; for(int i=1 ; i<=m ; i++) { int x = read(); int y = read(); printf("%d\n",ans[vis[x][y]]); } return 0; }
B. SEQUEL_Road
思路：
按照完全二分图的情况匹配是最优的（不会证明），姑且当做规律题。
当n为偶数时，平均分配的时候是上面n/2个点，下面n/2个点，所以是n/2*n/2
当n为奇数时，一边为n/2个点，另一边是n-n/2个点，乘积就是答案。
代码：
int main(){ int n; while(~scanf("%d",&n)){ int x=n/2; printf("%d\n",x*(n-x)); } return 0; }
C. 宝可梦
只是改了改题目背景，不知道为什么没人过。题解网上有很多，种类并查集or带权并查集都可。
D. 多娜多娜一起来坐高铁
E. 唐人街探案
签到题
F. 恐怖的咬手鲨鱼
wyb学长说是个逆尼姆博弈的板子题，然而博弈论一点也没有讲。
G. 欢欢的签到题
upd:题解
费马小定理求逆元
H. 欢欢的快速幂
出题人说是个欧拉定理，我不会所以就等到明天再更新~
upd:题解 把异或改成了和
I. 真的签到题
线段树区间修改区间求和，注意懒惰标记的优先级。
由于乘法的运算级高于加法，要保证在加法之前，将乘法进行完毕。
也就是说在修改时，要先将乘法的懒标下传，再将加法的懒标下传。
附上我11个月前写的lj代码：
#include<bits/stdc++.h> typedef long long ll; using namespace std; const int maxn=1e5+10; int n,m,w[maxn],p; struct node{ int l,r; ll sum,add,mul;//维护区间和和懒惰标记 }a[maxn*4]; void pushup(int u){ a[u].sum=(a[u<<1].sum+a[u<<1|1].sum)%p; } void qdown(node &t,int add,int mul){ t.sum=((ll)t.sum*mul+(ll)(t.r-t.l+1)*add)%p; t.mul=(ll)t.mul*mul%p; t.add=((ll)t.add*mul+add)%p;///也要考虑乘积的懒惰标记产生的影响 } void pushdown(int u){ qdown(a[u<<1],a[u].add,a[u].mul); qdown(a[u<<1|1],a[u].add,a[u].mul); a[u].add=0;a[u].mul=1;///注意乘积的懒惰标记传递后应当为1 } void build(int u,int l,int r){ if(l==r) a[u]={l,r,w[r],0,1}; else{ a[u]={l,r,0,0,1}; int mid=l+r >> 1; build(u<<1,l,mid);build(u<<1|1,mid+1,r); pushup(u); } } void update(int u,int l,int r,int add,int mul){ if(a[u].l>=l&&a[u].r<=r) qdown(a[u],add,mul); else{ pushdown(u); int mid=a[u].l+a[u].r >>1; if(l<=mid) update(u<<1,l,r,add,mul); if(r>mid) update(u<<1|1,l,r,add,mul); pushup(u); } } int qask(int u,int l,int r){ if(a[u].l>=l&&a[u].r<=r) return a[u].sum; pushdown(u); int mid=a[u].l+a[u].r >>1; int sum=0; if(l<=mid) sum=qask(u<<1,l,r); if(r>mid) sum=(sum+qask(u<<1|1,l,r))%p; return sum; } int main(){ scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;i++) scanf("%d",&w[i]); build(1,1,n); while(m--){ int op,l,r,v; scanf("%d%d%d",&op,&l,&r); if(op==1){ scanf("%d",&v); update(1,l,r,0,v); } else if(op==2){ scanf("%d",&v); update(1,l,r,v,1); } else printf("%d\n",qask(1,l,r)); } return 0; }
J. 学呀学呀学矩形
唯一分解定理
代码;
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod=9999991; const int MAXM=50000+10; const int MAXN=1000000+10; ll p[MAXN], c[MAXN], cnt; ll qpow(ll n, ll m) { ll ans = 1; while(m) { if(m & 1) ans = ans*n% mod; n = n*n%mod; m >>= 1; } return ans%mod; } void deal(ll a) { for(int i=2;i<=a;i ++) { if(a % i == 0) { p[cnt++] = i; while(a % i == 0) { a /= i; c[i] ++; } } } } int main() { int a,b; cin>>a>>b; deal(a); ll ans = 1; for(int i=0;i<cnt;i++) ans =(ans%mod*((qpow(p[i], b*c[p[i]]+1)-1+mod)%mod))%mod*(qpow(p[i]-1,mod-2)%mod)%mod; cout<<(ans+mod)%mod<<endl; fclose; }
K. 小明的疑惑
这是假的签到题吧，当时icpc模拟赛被卡了好久的题。
L. 如何优雅的写单词
正解是kmp，数据出水了所以暴力也能过。
upd:题解
代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+7; int n,k; char p[107]; int net[maxn]; void kmp_next(){ net[0]=0; net[1]=0; for(int j=1;j<n;j++){ int k = net[j]; while(p[j] != p[k] && k) k = net[k]; if(p[j] == p[k]) net[j+1] = k+1; else net[j+1] = 0; } } int main(){ /// freopen("1.in","r",stdin); /// freopen("1.out","w",stdout); cin >> n >> k; cin >> p; kmp_next(); ///for(int i=1;i<=n;i++) printf("%d ",net[i]); ///puts(""); cout<<p; for(int i=1;i<k;i++){ for(int j=net[n];j<n;j++) printf("%c",p[j]); } return 0; }
