T1
记表示走i步，第i步结尾是向北的方案数
记表示走i步的方案数
那么
然后高精搞一搞
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int m[2333][2333]; int sx,sy,n,ans; const int dx[]={1,-1,0}; const int dy[]={0,0,-1}; int px[2333],py[2333],f[2333],g[2333]; void dfs(int x,int y,int tm,int px[],int py[]){ if(tm==n){ printf("Found path: "); for(int i=1;i<=tm;i++)printf("(%d,%d)",px[i],py[i]);printf("(%d,%d)",x,y);puts(""); ans++; }else for(int i=0;i<3;i++){ int nx=x+dx[i],ny=y+dy[i]; if(!m[nx][ny]&&(nx!=px[tm]||ny!=py[tm])){ //printf("(%d,%d)->(%d,%d) ",x,y,nx,ny); m[nx][ny]=1; px[tm+1]=x;py[tm+1]=y; dfs(nx,ny,tm+1,px,py); m[nx][ny]=0; } } } struct Bn{ int f[2333],len; }; Bn cheng2(Bn a){ Bn c;c.len=a.len; memset(c.f,0,sizeof(c.f)); for(int i=1;i<=c.len;i++)c.f[i]=a.f[i]*2; for(int i=1;i<=c.len;i++)c.f[i+1]=c.f[i]/10+c.f[i+1],c.f[i]%=10; while(c.f[c.len+1]>0){ c.f[c.len+1]+=c.f[c.len]/10; c.f[c.len]%=10; ++c.len; } return c; } Bn jia(Bn a,Bn b){ Bn c;c.len=max(a.len,b.len); memset(c.f,0,sizeof(c.f)); for(int i=1;i<=c.len;i++){ c.f[i]+=a.f[i]+b.f[i]; c.f[i+1]=c.f[i]/10; c.f[i]%=10; } while(c.f[c.len+1]>0){ c.f[c.len+1]+=c.f[c.len]/10; c.f[c.len]%=10; ++c.len; } return c; } Bn F[101]; void test(){ F[1].f[1]=3;F[1].len=1; F[0].f[1]=1;F[0].len=1; for(int i=2;i<=n;i++){ F[i]=jia(cheng2(F[(i-1)]),F[(i-2)]); } for(int i=F[n].len;i>=1;i--)cout<<F[n].f[i];puts(""); } int main(){ freopen("game.in","r",stdin); freopen("game.out","w",stdout); scanf("%d",&n); //f[1]=3;f[0]=1; // for(int i=2;i<=n;i++){ // f[i]=f[i-1]*2+f[i-2]; // } //printf("%d ",f[n]); //shorter digits //Bigenumber test(); return 0; }
T2
随便建下树就好了
#include<stack> #include<queue> #include<cstdio> #include<cstring> #include<iostream> using namespace std; char s[350000]; struct edge{ int to,next; }e[66666];int cnt,last[33333]; int boolean[33333]; void link(int a,int b){ //printf("~~~%d %d ",a,b); e[++cnt]=(edge){b,last[a]};last[a]=cnt; e[++cnt]=(edge){a,last[b]};last[b]=cnt; } void initial(){ memset(last,0,sizeof(last)); cnt=0; } int L[32003],R[32003],qzh[32003],isl[32003]; bool q(int r,int l){ } void Cpare(){ puts("--------------------"); int n=strlen(s+1),_L=0,_R=0; stack<int>st; for(int i=1;i<=n;i++){ if(s[i]=='('){ st.push(i); } if(s[i]==')'){ L[st.top()]=i; st.pop(); } } for(int i=1;i<=n;i++)cout<<L[i]<<endl; for(int i=1;i<=n;i++)qzh[i]=qzh[i-1]+(s[i]=='('||s[i]==')'); for(int i=1;i<=n;i++)if(L[i])isl[i]=qzh[L[i]]-qzh[i-1]-2; for(int i=1;i<=n;i++)if(L[i])cout<<"~"<<isl[i]<<endl;cout<<endl; puts("--------------------"); }//debug int CaseCnt; struct data{ int u,d,fa; }; int dep[333333]; void bfs(){ queue<data>q; q.push((data){1,dep[1]=1,-1}); while(!q.empty()){ data c=q.front();q.pop(); for(int i=last[c.u];i;i=e[i].next){ if(e[i].to!=c.fa){ dep[e[i].to]=dep[c.u]+1; q.push((data){ e[i].to,c.d+1,c.u}); } } } } int main(){ freopen("form.in","r",stdin); freopen("form.out","w",stdout); while(scanf("%s",s+1)!=EOF){ initial(); if(strlen(s+1)==2&&s[1]=='('&&s[2]==')')return 0; int n=strlen(s+1); s[0]='R'; stack<char>st,st2; //Cpare(); int _n=0; memset(boolean,-1,sizeof(boolean)); for(int i=1;i<=n;i++){ if(s[i]=='(' ){ if(!st.empty()){ link(st.top(),_n+1); } st.push(++_n); } if(s[i]=='F'||s[i]=='T'){ if((s[i-1]!='F'&&s[i-1]!='T')&& (s[i+1]!='F'&&s[i+1]!='T')){ //puts("GS");//get stuck boolean[_n+1]=(s[i]=='T'); link(st.top(),_n+1);_n++; }else{ boolean[_n+1]=(s[i]=='T'); link(st.top(),++_n); } } if(s[i]==')')st.pop(); } n=_n; bfs(); // cerr<<"GS";//got safely for(int i=n;i>=1;i--){ if(boolean[i]==-1){ if(last[i])boolean[i]=boolean[e[last[i]].to]; if(dep[i]&1){ for(int v=e[last[i]].next;v;v=e[v].next) if(dep[e[v].to]>dep[i]) boolean[i]=boolean[i]&&boolean[e[v].to]; } else for(int v=e[last[i]].next;v;v=e[v].next) if(dep[e[v].to]>dep[i]){ boolean[i]=boolean[i]||boolean[e[v].to]; } } //cout<<boolean[i]<<' '; }//puts(""); printf("%d. ",++CaseCnt); if(boolean[1])printf("true"); else printf("false"); puts(""); } return 0; }
T3
同：BZOJ1041圆上的整点
#include<map> #include<stack> #include<queue> #include<cstdio> #include<string> #include<vector> #include<cstring> #include<complex> #include<iostream> #include<assert.h> #include<algorithm> using namespace std; #define inf 1001001001 #define infll 1001001001001001001LL #define FOR0(i,n) for(int (i)=0;(i)<(n);++(i)) #define FOR1(i,n) for(int (i)=1;(i)<=(n);++(i)) #define ll long long #define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl #define gmax(a,b) (a)=max((a),(b)) #define gmin(a,b) (a)=min((a),(b)) #define ios0 ios_base::sync_with_stdio(0) #define Ri register int #define gc getchar() #define il inline il int read(){ bool f=true; ll x=0;char ch; while(!isdigit(ch=gc))if(ch=='-')f=false; while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=gc;} return f?x:-x; } #define gi read() #define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout); double eps=1e-10; ll n,m,r,ans; ll pf(ll x){ return x*x; } void get(ll d,ll a,double b){ ll t=b; if(b-t!=0||__gcd(a,t)!=1||a==t){ return; } ll y=d*a*t,x;x=(ll)sqrt(pf(r)-pf(y)); if(x>=n||y>=m)return; ans+=(n-x)*(m-y)*2; } int main(){ FO(dist); n=gi;m=gi; int t=gi; while(t--){ r=gi; ans=0; if(pf(r)>pf(n-1)+pf(m-1)){ printf("0 ");continue; } if(r<n)ans=ans+m*n-m*r; if(r<m)ans=ans+m*n-n*r; for(ll d=1;pf(d)<=2*r;d++){ if(2*r%d==0){ for(ll a=1;pf(a)<=r/d;a++)get(d,a,sqrt(2*r/d-pf(a))); if(d!=2*r/d) for(ll a=1;pf(a)<=d/2;a++){ get(2*r/d,a,sqrt(d-pf(a))); } } } cout<<ans<<' '; } }