首页 > 代码库 > OI队内测试——石门一
OI队内测试——石门一
T1:
题目大意：
给你一个立方体，每个面上有些数字，给你一个数字K，你可以玩K轮游戏，
每轮你会将每个面上的数均分为4份，分给相邻的面，求K轮游戏后，上面的数字是
依次给你前、后、上、下、左、右的起始数字大小！
题解：因为轮数最大只有45，所以直接暴力模拟即可，但是可能是数据水，在通分的时候不会爆炸，也可能是我太垃圾不会算最坏情况！
总之非高精度可以A
T2:
题目大意：
给你一串由小写字母组成的字符串，希望你把它划分成一些小段，使得每一小段字符串
中的字母都不相同，并且希望分的段数尽量少。
字符串"nnsmpmn"，最少分成 3 小段："n","nsmp","mn"。 排序后输出：mn n nsmp
可能有多组解，求最小字典序的答案并输出
题解：DP，设F[i]表示到第i段截至的struct 存下段数，每段的字符组成即可！
T3：
题目大意：
你和朋友 Shary 玩一个游戏：在一个无环的、无向的图中，每个节点可以放一些糖果。
每次 Shary 可以从糖果数不少于 2 的节点上拿 2 个糖果，吃掉 1 个，并把另一个糖果放到相 邻的某个节点去。
如果在某个时候，目标节点 T 上有了糖果，游戏结束，Shary 赢。
如果你设计的初始状态，无论如何 Shary 都赢不了，则 Shary 输。 给定一个图，你能赢的方案中可以放的最多糖果数是多少？如果答案数超过 2*10^9， 只要输出-1 即可
题解：贪心即可，考虑它一定是一棵树，于是以这个节点T为根，先考虑一条链，我们可以证明在深度最大的放2*size+1个，其余点不放是最优的
因为链与树无本质上的区别，所以重复上述操作即可！
#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdio> #define ll long long using namespace std; ll read() { ll x=0,f=1; char ch; while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1; while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘); return x*f; } ll gcd(ll a,ll b){if (!b) return a; return gcd(b,a%b); } struct point{ ll x,y; friend point operator / (point a,ll x){ if ((a.x%x)==0) {a.x/=x; return a;} else{ a.y*=x; ll tmp=gcd(a.x,a.y); a.x/=tmp; a.y/=tmp; return a; } } friend point operator + (point a,point b){ if (a.x==0) return b; if (b.x==0) return a; ll tmp=gcd(b.y,a.y); tmp=a.y/tmp*b.y; a.x*=(tmp/a.y); b.x*=(tmp/b.y); a.y=b.y=tmp; point c; c.x=a.x+b.x; c.y=1; return (c/tmp); } }a[7],b[7]; int main() { freopen("cube.in","r",stdin); freopen("cube.out","w",stdout); point x,y; x.x=1; x.y=4; y.x=1; y.y=3; for (int i=1; i<=6; i++) a[i].x=read(),a[i].y=1; int k=read(); //if (k==0) {cout<<a[3].x<<endl; return;} for (int i=1; i<=k; i++) { b[1]=b[2]=(a[5]+a[6]+a[3]+a[4])/4; b[3]=b[4]=(a[1]+a[2]+a[5]+a[6])/4; b[5]=b[6]=(a[1]+a[2]+a[3]+a[4])/4; for (int j=1; j<=6; j++) a[j]=b[j]; } if (a[3].x==0) cout<<0<<endl; else if (a[3].x%a[3].y==0) cout<<a[3].x/a[3].y<<endl; else cout<<a[3].x<<"/"<<a[3].y<<endl; return 0; } /* 0 0 4 0 0 0 2 0 0 4 0 0 0 3 1 2 3 4 5 6 45 */
#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdio> #define N 55 using namespace std; struct Str{int x; char s[N];}; struct P{int cnt; Str s[N];}F[N]; bool vis[N]; int n; char s[N]; bool operator <(Str a,Str b) { for (int i=1; i<=min(a.x,b.x); i++) { if (a.s[i]==b.s[i]) continue; if (a.s[i]<b.s[i]) return 1; else return 0; } return a.x<b.x?1:0; } bool operator <(P a, P b){ if (a.cnt<b.cnt) return 1; if (a.cnt>b.cnt) return 0; for (int i=1; i<=a.cnt; i++) { if (a.s[i]<b.s[i]) return 1; if (b.s[i]<a.s[i]) return 0; } } int read() { int x=0,f=1; char ch; while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1; while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘); return x*f; } int main() { freopen("string.in","r",stdin); freopen("string.out","w",stdout); int T=read(); while (T--) { scanf("%s",s+1); n=strlen(s+1); for (int i=1; i<=n; i++) F[i].cnt=n+1; for (int i=1; i<=n; i++) { memset(vis,0,sizeof(vis)); for (int j=i-1; j>=0; j--) { if (vis[s[j+1]-‘a‘]) break; vis[s[j+1]-‘a‘]=1; P X; X=F[j]; X.cnt++; for (int k=j+1; k<=i; k++) X.s[X.cnt].x++,X.s[X.cnt].s[k-j]=s[k]; sort(X.s+1,X.s+1+X.cnt); if (X<F[i]) F[i]=X; } } // cout<<" "<<F[n].cnt<<" "<<F[n].s[]endl; for (int i=1; i<=F[n].cnt; i++) { for (int j=1; j<=F[n].s[i].x; j++) { cout<<F[n].s[i].s[j]; } cout<<" "; } cout<<endl; } return 0; } /* 2 facetiously aaaaa 2 aba babb */
#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdio> #define inf 2e9 #define ll long long #define N 100 using namespace std; char ch[N]; int pre[N*N],now[N],v[N*N],tot; int size[N],hson[N]; bool vis[N]; int n; ll ans; int read() { int x=0,f=1; char ch; while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1; while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘); return x*f; } void ins(int a,int b){++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; } void dfs(int x,int fa) { vis[x]=1; size[x]=1; for (int p=now[x]; p; p=pre[p]) { int son=v[p]; if (son==fa) continue; dfs(son,x); size[x]=max(size[x],size[son]+1); if (size[son]>size[hson[x]] || hson[x]==0) hson[x]=son; } } void get(int x,int fa,ll sum) { //cout<<" "<<x<<" "<<fa<<" "<<sum<<endl; if (ans==-1 || sum==-1) {ans=-1; return ;} if (!hson[x]) {ans+=sum; ans=ans>inf?-1:ans; return;} for (int p=now[x]; p; p=pre[p]) { int son=v[p]; if (son==fa) continue; if (son==hson[x]) get(son,x,sum*2+1>inf?-1:sum*2+1); else get(son,x,1); } } int main() { freopen("candy.in","r",stdin); freopen("candy.out","w",stdout); int T=read(); while (T--) { tot=0; memset(now,0,sizeof(now)); n=read(); int s=read(); s++; for (int i=1; i<=n; i++) { scanf("%s",ch+1); for (int j=1; j<=n; j++) if (ch[j]==‘Y‘) ins(i,j); } memset(vis,0,sizeof(vis)); memset(hson,0,sizeof(hson)); dfs(s,0); bool bo=true; for (int i=1; i<=n; i++) if (!vis[i]) bo=false; if (!bo) {cout<<-1<<endl; continue;} ans=0; get(s,0,0); printf("%lld\n",ans); } return 0; } /* 3 3 2 NYN YNY NYN 4 1 NYYY YNNN YNNN YNNN 7 0 NYNNNYN YNYNYNN NYNYNNN NNYNNNN NYNNNNN YNNNNNY NNNNNYN */
OI队内测试——石门一
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。