题意：Q次询问，每次给出N，M，Mod，问你有多少种排列，满足前面M个数字排序之后整个序列的LIS>=N-1。
思路：我们把数字看成[1,M]，[N-M+1,N]两个部分，假设是A和B。 题意说明最多有一个数字不在自己应该在的位置，那么有三种情况：
1，A在前面，B在后面：贡献是M!; 比如 （1 2， 3 4）； （2 1，3 ，4）...
2，A中有一个跑到了后面，剩下的按顺序放：M！* M*(N-M)； 比如(1 3, 2 4); (4 1, 2 3 )...
#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=110; int main() { ll T,N,M,C=0,Mod,ans; scanf("%lld",&T); while(T--){ scanf("%lld%lld%lld",&N,&M,&Mod); if(M>=N-1){ ans=1; rep(i,1,N) ans=(ll)ans*i%Mod; } else { ans=1; ll t=((N-M)*(N-M-1)+M*(N-M)+1)%Mod; rep(i,1,M) ans=(ll)ans*i%Mod; ans=(ll)ans*t%Mod; } printf("Case #%lld: %lld\n",++C,ans); } return 0; }
题意：在二维平面上四种操作： 1，加一个带权的点； 2，删去一个点； 3，给一个点周围欧几里得距离为sqrt(k)的存在的点点权都加w； 4，查询一个到点欧几里得距离为sqrtk的点权和。
思路：发现到一个点的欧几里得距离为k的点并不多。所以我们暴力即可。 注意用 ll。
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define mp make_pair #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxm=10000000; const int maxn=6010; ll a[maxn][maxn];int vis[maxn][maxn],Ca,tot; vector<pii>G[maxm+10]; void init() { rep(i,0,3200){ rep(j,0,3200){ if(i*i+j*j>maxm) break; G[i*i+j*j].push_back(mp(i,j)); tot++; } } } void add(int x,int y,int w) { if(vis[x][y]!=Ca) a[x][y]=0,vis[x][y]=Ca; a[x][y]+=w; } void del(int x,int y) { vis[x][y]=0; a[x][y]=0; } void FCY(int x,int y,int w) { if(x<0||x>6000||y<0||y>6000) return ; if(vis[x][y]==Ca) a[x][y]+=w; } int query(int x,int y) { if(x<0||x>6000||y<0||y>6000) return 0; if(vis[x][y]==Ca) return a[x][y]; return 0; } void ADD(int x,int y,int k,int w) { for(int i=0;i<G[k].size();i++){ int dx=G[k][i].first,dy=G[k][i].second; FCY(x+dx,y+dy,w); if(dx!=0) FCY(x-dx,y+dy,w); if(dy!=0) FCY(x+dx,y-dy,w); if(dx!=0&&dy!=0) FCY(x-dx,y-dy,w); } } ll Query(int x,int y,int k) { ll res=0; for(int i=0;i<G[k].size();i++){ int dx=G[k][i].first,dy=G[k][i].second; res+=query(x+dx,y+dy); if(dx!=0) res+=query(x-dx,y+dy); if(dy!=0) res+=query(x+dx,y-dy); if(dx!=0&&dy!=0) res+=query(x-dx,y-dy); } return res; } int main() { int T,N,M,x,y,w,k,opt;ll ans; init(); scanf("%d",&T); while(T--){ scanf("%d%d",&N,&M); Ca++; ans=0; printf("Case #%d:\n",Ca); rep(i,1,N){ scanf("%d%d%d",&x,&y,&w); add(x,y,w); } rep(i,1,M){ scanf("%d%d%d",&opt,&x,&y); x=(x+ans)%6000+1; y=(y+ans)%6000+1; if(opt==1){ scanf("%d",&w); add(x,y,w); } else if(opt==2){ del(x,y); } else if(opt==3){ scanf("%d%d",&k,&w); ADD(x,y,k,w); } else { scanf("%d",&k); printf("%lld\n",ans=Query(x,y,k)); } } } return 0; }
题意：约瑟夫问题，给定N，K，M，问第M个出来的人的编号是。 K或者M<1e6；
思路：只要知道公式就大概知道怎么做的题。
我们知道第N个人出来的编号公式是： p=0 ; rep(i,1,N) p=(p+k)%i; ans=p;（假设从0开始）
而第M个出来的人的编号，我们可以假设已经进行了N-M轮，但其实我们并不关心他们的位置，我可以做完之后把他们放到对应位置即可。
所以第M个人的编号是：p=0；rep(i,1,M) p=(p+k)%(i+N-M);
当M比较小时，可以直接求； 当K比较小时，我们可以利用整除合并的思想做。
#include<bits/stdc++.h> #define ll long long #define rep(i,a,b) for(ll i=a;i<=b;i++) using namespace std; ll solve(ll N,ll M,ll K) //N个人，每K个skip一次，第M次skip的是谁 { if(K==1) return M; ll p=0; if(M<=K){ rep(i,1,M){ p=(p+K-1)%(i+N-M)+1; } } else { ll tM=M; rep(i,1,M){ if(!tM) break; if(p+K-1>=i+N-M) tM--,p=(p+K-1)%(i+N-M)+1;//,cout<<i<<":"<<p<<endl; else { //p+kx-1<i+x-1+N-M -> x<(i-1+N-M-p)/(k-1); ll t=(i+N-M-p)/(K-1),g; if((i+N-M-p)%(K-1)==0) t--; g=min(t,tM); p=p+K*g; tM-=g; i=i+g-1; } } } return p; } int main() { int T,Ca=0; ll N,M,K; scanf("%d",&T); while(T--){ scanf("%lld%lld%lld",&N,&M,&K); printf("Case #%d: %lld\n",++Ca,solve(N,M,K)); } return 0; }
题意：开了一些变量，问你用了多少内存。
思路：模拟即可。
#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=200010; const int mod=1e9+7; char c[1000],a[10]={‘l‘,‘o‘,‘n‘,‘g‘,‘ ‘,‘l‘,‘o‘,‘n‘,‘g‘}; char b[12]={‘l‘,‘o‘,‘n‘,‘g‘,‘ ‘,‘d‘,‘o‘,‘u‘,‘b‘,‘l‘,‘e‘}; ll sum=0; int L; bool check1() { bool F=true; if(L<9) return false; rep(i,0,8) if(c[i]!=a[i]) return false; return true; } bool check2() { bool F=true; if(L<11) return false; rep(i,0,10) if(c[i]!=b[i]) return false; return true; } void solve() { ll tmp; L=strlen(c); if(c[0]==‘b‘||c[0]==‘c‘) tmp=1; if(c[0]==‘i‘||c[0]==‘f‘) tmp=4; if(check1()||c[0]==‘d‘) tmp=8; if(c[0]==‘_‘||check2()) tmp=16; rep(i,0,L-1){ if(c[i]==‘[‘){ int k=0; rep(j,i+1,L-1) if(c[j]>=‘0‘&&c[j]<=‘9‘) k=k*10+c[j]-‘0‘; tmp*=k; break; } } sum+=tmp; } int main() { int T,N,Ca=0; scanf("%d",&T); while(T--){ scanf("%d\n",&N); sum=0; rep(i,1,N){ gets(c); solve(); } ll F=sum/1024; if(sum%1024) F++; printf("Case #%d: %lld\n",++Ca,F); } return 0; }
Gym.101955: Asia Shenyang Regional Contest(寒假自训第10场)
原文：https://www.cnblogs.com/hua-dong/p/10363254.html