第二届太原理工大学程序设计新生赛决赛（重现赛）(A 博弈,C 栈模拟,D dfs输出模拟,E 扩展欧几里得 G 简单树问题,H dp,I 思维 J 思维 ,L 模拟,M 暴力 or三分)ccsudeer-

单开排名还是高点

A-Reversi

简单博弈

当两边有黑色的 时候 Qiy win 否则Vanis win

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;   inline ll read() {     ll x=0,w=1; char c=getchar();     while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}     while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}     return w==1?x:-x; } const int N=1e6+10; char s[N]; int n; int main() {     cin>>n>>s+1;     if(s[1]=='1'||s[n]=='1') puts("Qiy win");     else puts("Vanis win"); }

C-Nitori and Stack-Tech

做法：简单栈模拟，栈顶没有数 或者栈顶不等于当前t[i]  则入栈，否则出栈即可。

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;   inline ll read() {     ll x=0,w=1; char c=getchar();     while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}     while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}     return w==1?x:-x; } const int N=30; char s[N],t[N]; int n; int main() {     cin>>n>>s+1>>t+1;     stack<char>sta;     sta.push(s[1]);     int now=1,id=1;     int flag=1;     while(id<=n&&flag){         if(sta.size()&&sta.top()==t[id])++id,sta.pop();         else {             if(now<=n) sta.push(s[now++]);             else flag=0;         }     }     printf("%sn",flag?"Yes":"No"); }

D-Triangle

做法:简单的输出模拟，dfs一下，记录每个三角形左上角的坐标，然后一直dfs  直到最小的三角形（高度为2）

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=1e4+10; char s[N][N]; int f[20],n; void dfs(int x,int y,int len) {     if(len==2){         //printf("x:%d y:%dn",x,y);         s[x][y]='/';         s[x][y+1]='\';         s[x+1][y-1]='/';         s[x+1][y]='_';         s[x+1][y+1]='_';         s[x+1][y+2]='\';         return ;     }     dfs(x,y,len/2);     dfs(x+len/2,y-len/2,len/2);     dfs(x+len/2,y+len/2,len/2); } int main() {     f[0]=1;     for(int i=1;i<=12;++i) f[i]=f[i-1]*2;     n=read();     rep(i,1,f[n+1]) rep(j,1,f[n+1]) s[i][j]='.';      dfs(1,f[n],f[n]);      rep(i,1,f[n]) {         rep(j,1,f[n+1]-f[n]+i) printf("%c",s[i][j]);         puts("");     }  } 

E-Sweet

 

做法：好题一个，看到很多人代码O(a) O(b)也能过  一个好题因为数据不太好，差点沦为假题。做法参考自官方题解：

很妙。。

顺手贴一个exgcd的推导过程

 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll gcd(ll a,ll b) {     return b?gcd(b,a%b):a; } ll exgcd(ll a,ll b,ll &x,ll &y){     if(b==0){x=1;y=0;         return a;     }     ll r=exgcd(b,a%b,x,y);     ll temp=x;     x=y;     y=temp-(a/b)*y;     return r; }  ll n,a,b; int main() {     cin>>n>>a>>b;     ll c=n+1;     //ax+by=c x>=0 y>=0 的组数解      ll x,y;     ll gc=exgcd(a,b,x,y);//gc是a和b的 最小公倍数     if(c%gc!=0){puts("0");return 0;}//无解      ll x1=x*(c/gc),mod=b/gc;//x乘上c/gc的x1才是当前c真正的解          x1=(x1%mod+mod)%mod;//最小正整数解     if(x1==0) x1=mod;     //printf("x1:%lldn",x1);     //ll y1=(c-a*x1)/b;//为什么不除这个b？ a*x1+b*y1=c  除了就是某一个解了     ll y1=(c-a*x1);//为什么不除这个b？答案y最大的上界y1      ll ans,lcm=a*b/gc;     if(y1<0) ans = 0;     else ans = (y1%lcm)?y1/lcm+1:y1/lcm;//lcm是 公共解的位置     printf("%lldn",ans); } 

G-Gangstar

做法：枚举x的祖先节点 代表 x走到这个节点，然后往这个节点最深的节点去走，当然要判断走到这个祖先节点之前能否不被抓住。水题

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=1e6+10; vector<int>G[N]; int mx[N],dep[N],son[N]; int n,x,ans; int dfs(int u,int fa) {     dep[u]=dep[fa]+1;     for(int v:G[u]){         if(v==fa) continue;         son[u]|=dfs(v,u);         mx[u]=max(mx[u],mx[v]+1);     }     if(u==x) son[u]=1;     return son[u]; } void dfs1(int u,int fa) {     if(son[u]&&dep[x]-dep[u]<dep[u]-dep[1]){         //printf("u:%d %dn",u,2*dep[u]-dep[1]-dep[x]+mx[u]);          ans=max((dep[u]-dep[1]+mx[u])*2,ans);     }      for(int v:G[u]) if(v!=fa) dfs1(v,u);  } int main() {     cin>>n>>x;     rep(i,2,n) {         int u=read(),v=read();         G[u].push_back(v);         G[v].push_back(u);     }     int t=dfs(1,0);     dfs1(1,0);      printf("%dn",ans); }  

H-Stable Fusion

做法:二维dp  dp[i][j]代表i节点 能量值为j时子树合法时的最小代价。

那么状态转移方程：

 for(int i=0;i<=1000;++i){     mi=min(mi,dp[v][i]);     dp[u][i]=dp[u][i]+mi; }

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=1e3+10; vector<int>G[N];  int n; ll ans,a[N],dp[N][N]; void dfs(int u,int fa) {     for(int i=0;i<=1000;++i) dp[u][i]=abs(a[u]-i);     for(int v:G[u]){         if(v==fa) continue;         dfs(v,u);         ll mi=1000000000000;         for(int i=0;i<=1000;++i){             mi=min(mi,dp[v][i]);             dp[u][i]=dp[u][i]+mi;         }     } } int main() {     cin>>n;     for(int i=2;i<=n;++i){         int v=read();         G[i].push_back(v);         G[v].push_back(i);     }     rep(i,1,n) cin>>a[i];     dfs(1,1);      ans=10000000000000;     for(int i=0;i<=1000;++i) ans=min(ans,dp[1][i]);     printf("%dn",ans); } 

I-The Flower of Hope

做法：这题看起来难，其实很简单。简单分析   其实就是问有多少个区间的和大于等于m，权值没有负数  那么枚举 左端点，二分右端点即可。

 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; ll a[N],sum[N],m; int n; int main() {     scanf("%d%lld",&n,&m);     for(int i=1;i<=n;++i){         scanf("%lld",&a[i]);         sum[i]=sum[i-1]+a[i];     }     ll ans=0;      for(int i=1;i<=n;++i){         int l=i,r=n,res=n+1;         while(l<=r)         {             int mid=l+r>>1;             if(sum[mid]-sum[i-1]>=m) r=mid-1,res=mid;             else l=mid+1;         }         ans+=(n-res+1);      }     printf("%lldn",ans); } 

 

 

J-Fuse the Cube Fragment

做法：从大到小判断能否放进去 判断合法log的复杂度，这样能得到数量最多。

怎么输出另一个方案数，从已经得到的方案从大到小枚举，找到第一个非质数，得到他的最小素因数， 非质数除这个最小素因数代替这个非质数就得到了另一个方案数、

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;   inline ll read() {     ll x=0,w=1; char c=getchar();     while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}     while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}     return w==1?x:-x; } const int N=3e4+10; int vis[N],n,prime[N],len,vs[N]; vector<int>ans,ans1; void init() {     for(int i=2;i<N;++i){         if(!vs[i]) prime[++len]=i;         for(int j=1;j<=len&&i*prime[j]<N;++j){             vs[i*prime[j]]=prime[j];             if(i%prime[j]) break;         }     } } int main() {     init();     cin>>n;     for(int i=n;i>=1;--i){         int flag=1;         for(int j=i;j<=n&&flag;j+=i) if(vis[j]) flag=0;         if(flag) ans.push_back(i),vis[i]=1;     }     for(int v:ans) printf("%d ",v);         int flag=0;     for(int v:ans) {         if(!vs[v]||flag) {             ans1.push_back(v);             continue;         }         flag=1;         ans1.push_back(v/vs[v]);       }     puts("");     for(int v:ans1) printf("%d ",v);   }

L-The Scarborough Fair

做法：简单模拟一下就好了。。能购买就购买，剩余没购买的  就枚举从某一个币开始往后兑换即可。

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=1e3+10;  int n,a[4],vis[4],b[4]; int id(int i) {     if(i<=3) return i;     if(i==4) return 1;     return 2;  } int main() {     cin>>n>>a[1]>>a[2]>>a[3];     rep(i,1,n)     {         int t=read(),w=read();         vis[t]+=w;     }     rep(i,1,3){         int mi=min(vis[i],a[i]);         a[i]-=mi;         vis[i]-=mi;     }     rep(i,1,3) b[i]=a[i];        if(vis[1]&&vis[2]&&vis[3]) puts("NO");     else{         for(int i=1;i<=3;++i){             if(!vis[i]){                 rep(i,1,3) a[i]=b[i];                  a[id(i+1)]+=a[i]/2;                 if(a[id(i+1)]>=vis[id(i+1)]){                     a[id(i+1)]-=vis[id(i+1)];                      a[id(i+2)]+=a[id(i+1)]/2;                     if(a[id(i+2)]>=vis[id(i+2)]){                         puts("YES");                         return 0;                     }                 }             }         }         puts("NO");     } }  /* 1 6 0 2 2 3  */ 

M-Cappuccino ~ the end of journey

做法：数值比较小，直接暴力即可，数据大点的话可以考虑 列公式 然后三分做法。

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;   inline ll read() {     ll x=0,w=1; char c=getchar();     while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}     while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}     return w==1?x:-x; } int a,b,c,d;   int main() {     cin>>a>>b>>c>>d;     int ans=0;     for(int i=0;i<=100;++i){         for(int j=0;j<=100;++j){             if(i*a+j*b<=d){                 ans=max(ans,i+j*c);             }         }     }     printf("%dn",ans); }