这几天失眠时间都不太够，室友太会折腾了，感觉有点累，所以昨天的题解也没写，看晚上能不能补起来。
题意：给定N组数(xi,yi)，玩家轮流操作，每次玩家可以选择其中一组对其操作，可以把它减去一个数，或同时减去一个数，当玩家操作后出现了（0，0）则胜利。
思路：注意这里是出现(0,0)胜，而不是全都是(0,0)胜，所以我们不能简单的球sg，最后异或得到答案。
但是我们转化一下，如果玩家面对的全是(1,2) 或(2,1)，则他胜利，那么我们可以以这两个状态为起点得到sg函数，就转化为了nim博弈。 当然，前提是没有xi==yi的情况。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=210; int sg[maxn][maxn],vis[maxn]; void getsg() { rep(i,1,100) rep(j,1,100){ if(i==j) continue; memset(vis,0,sizeof(vis)); rep(k,1,min(i-1,j-1)) vis[sg[i-k][j-k]]=1; rep(k,1,i-1) if(i-k!=j) vis[sg[i-k][j]]=1; rep(k,1,j-1) if(i!=j-k) vis[sg[i][j-k]]=1; rep(k,0,10000) if(!vis[k]){ sg[i][j]=k; break; } } } int main() { int N,F=0,x,y,sum=0; getsg(); scanf("%d",&N); rep(i,1,N){ scanf("%d%d",&x,&y); sum^=sg[x][y]; if(x==y) F=1; } if(F||sum) puts("Y"); else puts("N"); return 0; }
题意：对于一个匹萨，限制横着切N刀，竖着切M刀，问最后披萨被分为了多少块。 保证不存在超过三刀相交在一点的情况，以及在角上相交的情况。
思路：我们发现，一刀的贡献是与它相交的直线数+1。 横线和竖线的交点=N*M。 横线和横线的交点=逆序对数。竖线与竖线一样。
所以求两次逆序对即可。
#include<bits/stdc++.h> #define ll long long #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=2000010; struct in{ int x,y; bool friend operator <(in w,in v) { return w.x<v.x;} }s[maxn]; int sum[maxn],b[maxn],tot; void add(int a,int N){ for(int i=a;i<=N;i+=(-i)&i) sum[i]++; } int query(int a){ int res=0; for(int i=a;i;i-=(-i)&i) res+=sum[i]; return res; } ll get(int N) { sort(s+1,s+N+1); ll res=0; rep(i,1,N) sum[i]=0,b[i]=s[i].y; sort(b+1,b+N+1); tot=unique(b+1,b+N+1)-(b+1); rep(i,1,N) s[i].y=lower_bound(b+1,b+N+1,s[i].y)-b; for(int i=N;i>=1;i--){ res+=query(s[i].y); add(s[i].y,N); }return res; } int main() { int N,M; ll ans=0; scanf("%d%d",&N,&M); scanf("%d%d",&N,&M); rep(i,1,N) scanf("%d%d",&s[i].x,&s[i].y); ans=get(N); rep(i,1,M) scanf("%d%d",&s[i].x,&s[i].y); ans+=get(M); ans+=(ll)N*M+N+M+1; printf("%lld\n",ans); return 0; }
题意：统计不是1的个数。
思路：。。。
#include<bits/stdc++.h> #define ll long long #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=2000010; int main() { int N,x,ans=0; scanf("%d",&N); rep(i,1,N) scanf("%d",&x),ans+=(x!=1); printf("%d\n",ans); return 0; }
Gym.101908 Brazil Subregional Programming Contest(寒假自训第六场)
原文：https://www.cnblogs.com/hua-dong/p/10350608.html
