第二届太原理工大学程序设计新生赛决赛（重现赛）(A 博弈,C 栈模拟,D dfs输出模拟,E 扩展欧几里得 G 简单树问题,H dp,I 思维 J 思维 ,L 模拟,M 暴力 or三分)
单开排名还是高点
A-Reversi
简单博弈
当两边有黑色的 时候 Qiy win 否则Vanis win
#pragma GCC optimize(2)
#include
#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
#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;stacksta;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("%s\n",flag?"Yes":"No");
} D-Triangle
做法:简单的输出模拟，dfs一下，记录每个三角形左上角的坐标，然后一直dfs 直到最小的三角形（高度为2）
#pragma GCC optimize(2)
#include
#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:%d\n",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
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:%lld\n",x1);//ll y1=(c-a*x1)/b;//为什么不除这个b？ a*x1+b*y1=c 除了就是某一个解了ll y1=(c-a*x1);//为什么不除这个b？答案y最大的上界y1ll ans,lcm=a*b/gc;if(y1<0) ans = 0;else ans = (y1%lcm)?y1/lcm+1:y1/lcm;//lcm是 公共解的位置printf("%lld\n",ans);
}
G-Gangstar
做法：枚举x的祖先节点 代表 x走到这个节点，然后往这个节点最深的节点去走，当然要判断走到这个祖先节点之前能否不被抓住。水题
#pragma GCC optimize(2)
#include
#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;
vectorG[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]>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("%d\n",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
#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;
vectorG[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("%d\n",ans);
}
I-The Flower of Hope
做法：这题看起来难，其实很简单。简单分析 其实就是问有多少个区间的和大于等于m，权值没有负数 那么枚举 左端点，二分右端点即可。
#include
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("%lld\n",ans);
}
J-Fuse the Cube Fragment
做法：从大到小判断能否放进去 判断合法log的复杂度，这样能得到数量最多。
怎么输出另一个方案数，从已经得到的方案从大到小枚举，找到第一个非质数，得到他的最小素因数， 非质数除这个最小素因数代替这个非质数就得到了另一个方案数、
#pragma GCC optimize(2)
#include
#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];
vectorans,ans1;
void init()
{for(int i=2;i>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
#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
#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("%d\n",ans);
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！