License Plate Recognition
#include <bits/stdc++.h> using namespace std; int T; char s[35][105]; int cnt[105]; int ansl[10],ansr[10]; int main(){ scanf("%d",&T); for (int tt=1;tt<=T;tt++){ memset(cnt,0,sizeof(cnt)); for (int i=1;i<=30;i++){ scanf("%s",s[i]+1); for (int j=1;j<=100;j++){ if (s[i][j]=='#') cnt[j]++; } } int pos=100; for (int i=7;i>=2;i--){ while (pos>=1 && !cnt[pos]) pos--; ansr[i]=pos; while (pos>=1 && cnt[pos]) pos--; ansl[i]=pos+1; } while (pos>=1 && !cnt[pos]) pos--; ansr[1]=pos; pos=1; while (pos<=100 && !cnt[pos]) pos++; ansl[1]=pos; printf("Case #%d:\n",tt); for (int i=1;i<=7;i++){ printf("%d %d\n",ansl[i],ansr[i]); } } return 0; }
Kanade Loves Maze Designing
#include<iostream> #include<cstring> #include<queue> #include<map> #include<set> #include<algorithm> #include<cmath> #include<vector> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pii; const int inf=0x3f3f3f3f; const double eps=1e-8; const int N=100010; const int mod1=1e9+7; const int mod2=1e9+9; const int val=19560929; int T; int n; int col[N],f[N]; ll _x1[N],_x2[N]; int cnt[N]; ll ans1,ans2,ans=0; int h[N],e[N<<1],ne[N<<1],idx; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void ADD(int x){ if(cnt[x]==0) ans++; cnt[x]++; } void DEL(int x){ if(cnt[x]==1) ans--; cnt[x]--; } void init(){ _x1[0]=1; _x2[0]=1; for(int i=1;i<=2000;i++){ _x1[i]=1ll*val*_x1[i-1]%mod1; _x2[i]=1ll*val*_x2[i-1]%mod2; } } void dfs(int x,int fa){ ADD(col[x]); f[x]=ans; for(int i=h[x];i!=-1;i=ne[i]){ int y=e[i]; if(y==fa) continue; dfs(y,x); } DEL(col[x]); } int main(){ cin.tie(0); cout.tie(0); cin>>T; init(); while(T--){ cin>>n; for(int i=1;i<=n;i++) h[i]=-1; for(int i=2;i<=n;i++){ int p; cin>>p; add(i,p); add(p,i); } for(int i=1;i<=n;i++) cin>>col[i]; for(int i=1;i<=n;i++){ dfs(i,-1); ans1=0,ans2=0; for(int j=1;j<=n;j++){ ans1=(ans1+1ll*f[j]*_x1[j-1]%mod1)%mod1; ans2=(ans2+1ll*f[j]*_x2[j-1]%mod2)%mod2; } cout<<ans1<<" "<<ans2<<endl; } } }