GDUT 寒假排位赛一

感想:过个年10多天没刷题,一开始连签到题都不是很顺利,而且一开始作死开了D题,结果全场有D,F两道题没人过,结果排在了3题尾,哭死。但这不是理由,最重要的原因是自己菜,而且寒假第一阶段所学的知识点还不会运用,因为寒假第一阶段是专题训练,每道题都有说考察什么知识点,而且这次排位赛E题考二分,我却想不到二分做,I题考优先队列,我却一直卡在那里,一直想模拟过程,B题考DP,我却一直想贪心,根本没有想到状态转移,C题却嫌麻烦,不想模拟,所以放弃。最终只做完三道签到题,被rank1差点7题的lyr大佬无情的锤爆
总而言之,题还是刷的比较少,不懂得系统的总结加以应用,好多只知道知识点,却不会应用到题目中去
【题目链接】:http://codeforces.com/group/NVaJtLaLjS/contest/238166
A.The Bucket List(签到题)
题意:给定N只奶牛,每只奶牛开始挤奶时间以及结束时间分别为s与t,以及每只奶牛在挤奶时间需要b只桶,问最多需要多少只桶?
思路:(由于题目数据1<= s,t <=1000,且保证在某个时刻只有一只奶牛开始挤奶或者结束挤奶,所以直接暴力就行)
复杂度O(1000)

#include using namespace std; typedef long long ll; int a[1005],b[1005]; int main() { int n,s,e,c; cin>>n; for(int i=1; i<=n; i++) { cin>>s>>e>>c; a[s]=b[e]=c; } int cnt=0,tmp=0,i; for(i=1; i<=1000; i++) { if(a[i]){ if(a[i]<=tmp) tmp-=a[i]; else{ cnt+=(a[i]-tmp); tmp=0; } } if(b[i]) { tmp+=b[i]; } } cout<

B. Teamwork(dp)
题意: 给定n只奶牛,每只奶牛有一个技能点,把1-n只奶牛连续分成多组,每组奶牛不超过k只,每只奶牛只能存在一组,且该组的奶牛技能点都会升高到与组里某只奶牛最高技能点一样,如何分配,求得n只奶牛总的技能点最大
思路: dp,dp[i]表示前i只奶牛总的最大技能点,而且第i只奶牛会会受到前面k只奶牛影响,复杂度O(n*k)
#include using namespace std; typedef long long ll; int a[10005],dp[10005]; int main() { int n,k; ll sum=0; cin>>n>>k; for(int i=1; i<=n; i++) cin>>a[i]; for(int i=1; i<=n; i++) { int maxx=-1; for(int j=1; j<=min(i,k); j++) { maxx=max(maxx,a[i-j+1]); dp[i]=max(dp[i],dp[i-j]+maxx*j); } } cout<

C. Mooyo Mooyo(联通块dfs+简单模拟)
题意: 有点类似于消消乐,如果相邻同颜色的超过k块,就消去,消完后,若底下为空,由于重力会掉下去,问最后无法可消去后的方阵
思路: 先dfs一次求得各自相邻同颜色的方块数,若是满足>=k,则再dfs一次消去,接着模拟掉落过程,记住在地图mp[ ][ ]最底层为第n行,而不是第0行,模拟时不要写错,重复以上操作,直到符合条件结束循环
#include using namespace std; char mp[105][15],vis[105][15]; int n,k,cnt; int dis[4][2]={1,0,0,1,-1,0,0,-1}; bool judge(int x,int y,char ch) { if(x<0||y<0||x>n||y>10||vis[x][y]||mp[x][y]!=ch) return false; else return true; } void dfs1(int x,int y,char ch) { vis[x][y]=1; for(int i=0; i<4; i++) { int nx=x+dis[i][0],ny=y+dis[i][1]; if(judge(nx,ny,ch)) { cnt++; dfs1(nx,ny,ch); } } } void dfs(int x,int y,char ch) { mp[x][y]='0'; for(int i=0; i<4; i++) { int nx=x+dis[i][0],ny=y+dis[i][1]; if(judge(nx,ny,ch)) dfs(nx,ny,ch); } } int main() { cin>>n>>k; for(int i=0; i>mp[i]; while(1) { int flag=0; for(int i=0; i=k){ dfs(i,j,mp[i][j]); flag=1; } } } for(int i=0; i<10&&flag; i++) { int t=n; for(int j=n-1; j>=0; j--) { if(mp[j][i]!='0') mp[--t][i]=mp[j][i]; } for(int j=t-1; j>=0; j--) mp[j][i]='0'; }if(!flag) break; } for(int i=0; i

D. Cowpatibility 不会…………
【GDUT 寒假排位赛一】E. Convention(二分)
题意: 给定N只牛与N只牛的到达时间,m只公交车,每只公交车有c个座位, 求牛最长的等待时间最小(保证cm>=n)
思路: 先sort,然后进行二分check,若等待时间为mid且能把n只牛运走,则r=mid,否则l=mid+1,注意最长等待时间并不是a[i]-a[i-1],而是a[i]-pre(pre为该俩公交车第一只牛到达的时间,而不是上一只牛到达的时间)
复杂度O(n
logn)
#include using namespace std; int a[100005]; int n,m,c; int judge(int mid) { int pre=a[1],cnt=1,seat=1; for(int i=2; i<=n; i++) { if(a[i]-pre>mid||seat==c) { seat=1; cnt++; pre=a[i]; } else { seat++; } } if(cnt<=m) return 1; return 0; } int main() { scanf("%d%d%d",&n,&m,&c); for(int i=1; i<=n; i++) scanf("%d",&a[i]); sort(a+1,a+1+n); int r=1000000000,l=0; while(r-l>0) { int mid=(l+r)/2; if(judge(mid)) r=mid; else l=mid+1; } printf("%d\n",r); return 0; }

F. Fine Dining 不会…………
G. Back and Forth(dfs)
题意: A,B两个仓库,一开始各有1000单位牛奶,与各有10只可以装牛奶的桶,桶的大小可能不一样。现在问第一天在仓库A随便选择一只桶装满牛奶,然后运到仓库B,第二天从仓库B中11只桶随便选择一只桶装满牛奶,运到仓库A,问经过这样的牛程两次之后仓库A的牛奶的量有多少种可能?
思路: 最多有10 * 11 * 11 * 11=13310中选择,然后dfs过程中进行适当的剪枝,如相同型号的桶只取一次,最后A仓库的总量范围为0-2000,因为一开始A与B各有1000单位,遍历0-2000确定共有几种可能,注意dfs过程中记得回溯
#include using namespace std; int a[105],b[105],num,c[2005]; void dfs(int t,int suma,int sumb) { if(t>4){ c[suma]=1; return; } if(t%2){ for(int i=1; i<=100; i++) { if(a[i]){ b[i]++,a[i]--,t++; dfs(t,suma-i,sumb+i); a[i]++,b[i]--,t--; } } } else { for(int i=1; i<=100; i++) { if(b[i]){ a[i]++,b[i]--,t++; dfs(t,suma+i,sumb-i); b[i]++,a[i]--,t--; } } }} int main() { memset(c,0,sizeof c); for(int i=1; i<=10; i++) { cin>>num; a[num]++; } for(int i=1; i<=10; i++) { cin>>num; b[num]++; } dfs(1,1000,1000); int cnt=0; for(int i=0; i<=2000; i++) if(c[i]==1) cnt++; cout<

H.Mixing Milk(签到题)
题意: 有3只桶容量分别为c1,c2,c3,且一开始桶里的牛奶分别为m1,m2,m3,现在从A桶倒到B桶,B桶倒到C桶,C桶倒到A桶,每次倾倒要么倒空,要么倒满,问倒100次之后,三只桶里各有多少牛奶
思路: 每次倾倒两只桶的容量符合公式为m1-min(m1,c2-m2),m2+min(m1,c2-m2)
#include using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int MAXN = 105 + 5; int w[3],v[3]; void pour(int i, int j) { int del = min(w[j] - v[j], v[i]); v[i] -= del; v[j] += del; } int main() { for(int i = 0; i < 3; i++) { cin >> w[i] >> v[i]; } for(int i = 1; i <= 100; i++) { if(i % 3 == 1) { pour(0, 1); } else if(i % 3 == 2) { pour(1, 2); } else if(i % 3 == 0) { pour(2, 0); } } for(int i = 0; i < 3; i++) cout <

I. Convention II(优先队列)
题意: 给定编号为1-N的N头牛,与每只牛到达的时间,以及吃草的时间,且牛编号小的权限大,每次只能有一只牛在吃草,在此期间若有其他牛到达,则需要等待,若是有多只牛同时等待,则编号小的牛优先吃草,求牛的最长的等待时间
思路: 先把牛的到达时间进行sort,然后把需要等待的牛加入优先队列,每当一头牛吃完,再从队列里取出id最小的牛,若期间有其他牛到达,则加入队列,直到队列清空,则看后续是否牛到达,若有到达,则不用进入队列,无需等待,可以直接吃草,在取出队列的过程中要维护使得等待时间的最大
#include using namespace std; struct node { int s,v,id; bool operator <(node y)const{ return this->id>y.id; } }a[100005]; bool cmp(node x,node y) { if(x.s==y.s) return x.vque; int time=0,ans=0,k; for(int i=1; i<=n; i++) { if(que.empty()) { time=a[i].s+a[i].v; for(k=i+1; k<=n; k++) { if(a[k].s<=time) que.push(a[k]); else break; } } else { node tmp=que.top(); que.pop(); ans=max(ans,time-tmp.s); time+=tmp.v; for(; k<=n; k++) { if(a[k].s<=time) que.push(a[k]); else break; } } } printf("%d\n",ans); return 0; }

    推荐阅读