A
#include <bits/stdc++.h> using namespace std; int T,n,m; char s[1005]; int main() { scanf("%d",&T); while (T--) { scanf("%d%d%s",&n,&m,s); int c=0; for (int i=0;i<n;++i) { for (int j=0;j<m;++j) putchar(s[c++]); putchar(' '); } } return 0; }
B
斐波那契进位方法，加法模拟，注意答案唯一，需要把11变成100
#include <bits/stdc++.h> const long long mod = 1e9+7; const double ex = 1e-10; #define inf 0x3f3f3f3f using namespace std; int num[50][2000]; int ans[1000]; void change(int a[],int id){ if (a[id] == 0) a[id] = 1; else{ if (a[id-1] == 0){ int i; for ( i = id;i >= 0 && a[i] == 1 && a[i-1] == 0;i-=2); if (i>0){ if (a[i] == 0){ for (;i<=id;i++) a[i] = 1; return; } else{ for (i = i - 1;i<id-1;i++) a[i] = 0; a[id-1] = 1; a[id] = 1; } } } int num = 0; int j; for (j = id ; a[j] == 1; j++){ num++; } for (int i = j; i>id ; i-=2){ a[i] = 1; a[i-1] = 0; } if (num%2==1){ a[id] = 1; a[id-1] = 0; } } return; } void plu(int a[],int j){ for (int i = 0; i<=1000; i++) if (num[j][i] == 1) change(a,i); } void toans(int a[]){ for (int i = 0; i<=1000 ;i++){ if (a[i] == 1){ int j,k; for (j = i ;a[j]==1;j++); for (k = j ; k > i+1; k-=2){ a[k] = 1; a[k-1] = 0; } a[k] = 0; i = j-1; } } } int main() { num[0][500] = 1; for (int i = 1;i<=35;i++){ plu(num[i],i-1); plu(num[i],i-1); } int n; while (scanf("%d",&n)==1){ memset(ans,0,sizeof(ans)); for (int i = 0; i<=35;i++){ if (n%2){ plu(ans,i); } n/=2; } toans(ans); int b = 500,e = 500; int fla = 1; for (int i = 1000 ; i>=0;i--){ if (ans[i] == 1 && fla) b = i,fla = 0; if (ans[i]) e = i; } for (int i = b ; i >= e ; i--){ if (i == 499) printf("."); printf("%d",ans[i]); } puts(""); } return 0; }
C
二分
#include <bits/stdc++.h> using namespace std; const int maxn=1005; const int maxs=1111111; const double eps = 1e-10; int T,a[maxn],n,s1,s2,n1,n2,st1[maxs],st2[maxs]; long long sc; double p; bool check(int mid) { int r=s2-1; long long now=0; for (int i=0;i<s1;++i) { if (now>=sc) return true; if (st1[i]>mid) return false; while (r>=0&&st1[i]+st2[r]>mid) --r; now+=r+1; } if (now>=sc) return true; return false; } int main() { scanf("%d",&T); while (T--) { scanf("%d%lf",&n,&p); for (int i=0;i<n;++i) scanf("%d",&a[i]); sc=ceil((1LL<<n)*(p)-eps); n1=n/2; n2=n-n1; s1=1<<n1; s2=1<<n2; memset(st1,0,s1*sizeof st1[0]); memset(st2,0,s2*sizeof st2[0]); for (int i=0;i<s1;++i) for (int j=0;j<n1;++j) if (i&(1<<j)) st1[i]+=a[j]; for (int i=0;i<s2;++i) for (int j=0;j<n2;++j) if (i&(1<<j)) st2[i]+=a[j+n1]; sort(st1,st1+s1); sort(st2,st2+s2); int left=0,right=1000*n,res=0; while (left<=right) { int mid=(left+right)>>1; if (check(mid)) { res=mid; right=mid-1; } else left=mid+1; } printf("%d ",res); } return 0; }
G
二维线段树
#include <bits/stdc++.h> #define maxn 888 #define inf 0x3f3f3f3f #define REP(i,x,y) for(int i=x;i<(y);i++) #define RREP(i,x,y) for(int i=x;i>(y);i--) using namespace std; typedef long long ll; typedef pair<int,int> pii; int n; struct SegTree2D{ int maxx[maxn<<2][maxn<<2],minn[maxn<<2][maxn<<2],n,m; int xo,xleaf,x1,y1,x2,y2,x,y,v,vmax,vmin; void query1D(int o,int L,int R) { if(y1<=L&&R<=y2) { vmax=max(maxx[xo][o],vmax); vmin=min(minn[xo][o],vmin); } else { int M=(L+R)>>1; if(y1<=M) query1D(o*2,L,M); if(M<y2) query1D(o*2+1,M+1,R); } } void query2D(int o,int L,int R) { if(x1<=L&&R<=x2) { xo=o;query1D(1,1,m); } else { int M=(L+R)>>1; if(x1<=M) query2D(o*2,L,M); if(M<x2) query2D(o*2+1,M+1,R); } } void update1D(int o,int L,int R) { if(L==R) { if(xleaf) { maxx[xo][o]=minn[xo][o]=v;return ; } maxx[xo][o]=max(maxx[xo*2][o],maxx[xo*2+1][o]); minn[xo][o]=min(minn[xo*2][o],minn[xo*2+1][o]); } else { int M=(L+R)>>1; if(y<=M) update1D(o*2,L,M); else update1D(o*2+1,M+1,R); maxx[xo][o]=max(maxx[xo][o*2],maxx[xo][o*2+1]); minn[xo][o]=min(minn[xo][o*2],minn[xo][o*2+1]); } } void update2D(int o,int L,int R) { if(L==R) { xo=o;xleaf=1;update1D(1,1,m); } else { int M=(L+R)>>1; if(x<=M) update2D(o*2,L,M); else update2D(o*2+1,M+1,R); xo=o;xleaf=0;update1D(1,1,m); } } void query() {vmax=-inf;vmin=inf;query2D(1,1,n);} void update() {update2D(1,1,n);} }T; int main() { int TT;scanf("%d",&TT);int cas=1; while(TT--) { scanf("%d",&n); T.n=T.m=n; memset(T.maxx,0,sizeof(T.maxx));memset(T.minn,0,sizeof(T.minn)); REP(i,1,n+1) REP(j,1,n+1) { scanf("%d",&T.v); T.x=i;T.y=j; T.update(); T.x1=i;T.x2=i;T.y1=j;T.y2=j; T.query(); // cout<<"!"<<" "<<T.vmax<<" "<<T.vmin<<endl; } int q;scanf("%d",&q); printf("Case #%d: ",cas++); while(q--) { int x,y,L;scanf("%d %d %d",&x,&y,&L); int len=(L-1)/2; T.x1=max(1,x-len),T.y1=max(1,y-len); T.x2=min(x+len,n),T.y2=min(n,y+len); T.query(); // cout<<T.vmax<<" "<<T.vmin<<endl; T.v=(1LL*T.vmax+1LL*T.vmin)/2; T.x=x;T.y=y; T.update(); T.x1=x;T.x2=x;T.y1=y;T.y2=y; T.query(); //cout<<"!"<<" "<<T.vmax<<" "<<T.vmin<<endl; printf("%d ",T.v); } } }
I
字符串双哈希
#include <bits/stdc++.h> using namespace std; typedef pair<long long,long long> pll; const long long mod1=1e9+7; const long long mod2=1e9+9; const long long pow1=233; const long long pow2=131; const int maxn=100005; int m,l,n,flag,res; long long ha1[maxn],ha2[maxn],p1[maxn],p2[maxn]; pll temp[maxn]; char s[maxn]; map<pll,int> mp; inline pll Hash(int x,int l) { return pll((ha1[x+l-1]-ha1[x-1]+mod1)*p1[n-x]%mod1,(ha2[x+l-1]-ha2[x-1]+mod2)*p2[n-x]%mod2); } inline void check(int x) { mp.clear(); int cnt = 0; for (int i = 0 ; i<m; i++){ mp[Hash(x+i*l,l)]++; if (mp[Hash(x+i*l,l)]==2) cnt++; } int be = x; for (int en = x+m*l;en <= n+1; en+=l){ if (cnt == 0) res++; if (en+l <= n+1){ mp[Hash(be,l)]--; if (mp[Hash(be,l)] == 1) cnt--; mp[Hash(en,l)]++; if (mp[Hash(en,l)] == 2) cnt++; } be+=l; } } int main() { while (scanf("%d%d%s",&m,&l,s+1)==3) { n=strlen(s+1); ha1[0] = ha2[0] = 0; p1[0]=p2[0]=1; for (int i=1;i<=n;++i) { p1[i]=p1[i-1]*pow1%mod1; p2[i]=p2[i-1]*pow2%mod2; ha1[i]=(ha1[i-1]+s[i]*p1[i])%mod1; ha2[i]=(ha2[i-1]+s[i]*p2[i])%mod2; } res = 0; for (int i=1;i<=l;++i) check(i); printf("%d ",res); } return 0; }