GDUT 寒假排位赛二

直接看题 【题目链接】: http://codeforces.com/group/NVaJtLaLjS/contest/238204
A. Taming the Herd(签到题)
题意: 有一张表,记录奶牛出走的时间,若是当天奶牛出走,则当天记录为0,否则记录最近奶牛出走的时间,如奶牛是在三天前出走的,则当天记录为3,现在这张表出现破损,破损的地方记录为-1,问最多与最少奶牛出走的天数,若这张表记录不符合规则,则输出-1,且已知第一天奶牛必然出走
思路: 这道题需要注意的是题目所给的表不一定是正确的,如 样例-1 2 -1 -1 4 则输出-1,因为 第二天只可能是-1, 1

#include #define INF 0x3f3f3f3f using namespace std; typedef long long ll; int a[105],b[105]; int main() { int n; cin>>n; int num=0,cnt=0,flag=0; memset(b,-1,sizeof b); for(int i=1; i<=n; i++) cin>>a[i]; a[1]=0; for(int i=1; i<=n; i++) { if(a[i]!=-1) { if(i-a[i]>0){ if(a[i-a[i]]==-1||a[i-a[i]]==0) a[i-a[i]]=0; else { flag=1; } } else flag=1; } } if(flag){ cout<<"-1"<=1; ) { if(a[i]==0){ cnt++; i--; continue; } else if(a[i]!=-1) { i-=a[i]; continue; } i--; num++; } cout<

B. Hoofball(模拟)
题意: 有一群奶牛站成一列相互传球,传球规则是传给距离比较近的奶牛,若是左右两侧距离一样,则传给左侧的奶牛,问至少需要多少个球
思路: 这道有几种做法,有的是构建一个图,算出成环的个数,有的是模拟,有的是dp,都要开一个nxt[ ]存下每个球是传递目标。有一种比较好理解的就是从第一只奶牛开始传球,传到球就进行标记,从1-n遍历没有被标记的奶牛,每次做的标记不一样,如第一个球标记为1,第二个球标记为2,可以相互覆盖,最后统计还没有覆盖的标记种类,就是需要多少个球
#include using namespace std; const int N=1005; int n,a[N],vis[N],ans[N]; int cnt=1; void dfs(int pos) { if(vis[pos]==cnt)return; vis[pos]=cnt; if(pos==1)dfs(2); else if(pos==n)dfs(n-1); else if(pos!=1&&pos!=n){ if(a[pos]-a[pos-1]<=a[pos+1]-a[pos])dfs(pos-1); else dfs(pos+1); } } int main() { cin>>n; for(int i=1; i<=n; i++)cin>>a[i]; sort(a+1,a+1+n); for(int i=1; i<=n; i++){ if(!vis[i]) dfs(i); cnt++; } cnt=0; for(int i=1; i<=n; i++)ans[vis[i]]=1; for(int i=1; i<=n; i++)if(ans[i])cnt++; cout<

C. Rest Stops(贪心)
题意: 给出A和B两人每米需要走多少秒的速度,其中保证A的速度比B快,且需要A在整个路程一直在B前面,而在这段分布了N个草场,若待在草场时,每秒可以收获c单位草,问A走完这段路能收获多少单位草
思路: 每次取未走完路程中每秒可收获草的单位最大的草场
#include #define INF 0x3f3f3f3f using namespace std; typedef long long ll; struct node { int dis,c; }a[100005]; bool cmp(node a,node b) { if(a.c==b.c) return a.dis>b.dis; return a.c>b.c; } int main() {ll l,n,v1,v2,maxx=-1,id; cin>>l>>n>>v1>>v2; for(int i=1; i<=n; i++){ cin>>a[i].dis>>a[i].c; } ll ans=0; sort(a+1,a+1+n,cmp); //for(int i=1; i<=n; i++) // cout< id=a[1].dis; ans+=(v1-v2)*id*a[1].c; for(int i=2; i<=n; i++) { if(a[i].dis

D. Directory Traversal 连题意都看不懂……,更不会做
E. Taming the Herd (dp)
题意: 现在还是给出一张表,记录规则与A题一样(保证奶牛第一天肯定出走),但是现在这张表遭到修改,问奶牛1-n次出走的最小修改数
思路: 参照大佬的思路:
dp[ i ][ j ][ k ]表示已经到了第i天,逃了j次,今天计数器记的数为k的最小值。那么两种转移:
1、当k=0时,dp[ i ][ j ][ 0 ]=min ( dp[i?1][j?1][p] )+(a[i] != 0),
【GDUT 寒假排位赛二】2、当k!=0时,dp[ i ][ j ][ k ]=dp[i?1][ j ][k?1]+(a[i]!=k)
在第一条方程里,需要枚举p。所以复杂度是O(n^4)。 然后我们可以用一个g维护一下min(dp[i?1][j?1][p]),所以变成O(n^3)。
#include using namespace std; const int N=1e2+5; int dp[N][N][N],g[N][N],a[N]; int main() { int n; cin>>n; for(int i=1; i<=n; i++) cin>>a[i]; memset(dp,0x3f,sizeof dp); memset(g,0x3f,sizeof g); dp[0][0][0]=0; g[0][0]=0; for(int i=1; i<=n; i++) { for(int j=1; j<=i; j++) { for(int k=0; k

F. Teleportation(签到题)
题意: 略
思路: 略
G. Snow Boots(dp)
题意: 有一条路上面有N块瓷砖,每块瓷砖积雪深度不一,保证第一块瓷砖与最后一块瓷砖没有积雪,现在A光着脚站在第一块瓷砖,要走到第N块瓷砖,身上从有n双鞋子,按1-n排序,每次只能取最前面的一双鞋,每双鞋有两个属性,能承受最大的积雪深度,还有一次能跨越几块瓷砖,想要换新鞋子必须扔掉旧的或者直接扔掉最上面新的鞋
思路: 我们枚举当前用第i双靴子走路,用dp[j]示前i-1双靴子是否能走到第j块地砖,若dp[j]=true且deep[i]>=dis[j],说明第i双靴子可以在当前砖块被换上。那么我们就可以用第i双靴子去更新从第j块之后不超过step[i]块的砖块是否能到达。
有个大佬说一般n=250的数据 时间复杂度都是O(n^3)来着,反正这道题确实是。
#include using namespace std; int dp[255],dis[255],deep[255],step[255]; int main() { int n,m,ans; cin>>n>>m; for(int i=1; i<=n; i++) cin>>dis[i]; for(int i=1; i<=m; i++) { cin>>deep[i]>>step[i]; } dp[1]=1; for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { if(dp[j]&&dis[j]<=deep[i]) { for(int k=j; k<=min(n,j+step[i]); k++) { if(dis[k]<=deep[i]) dp[k]=1; } } } if(dp[n]) { ans=i; break; } } cout<

    推荐阅读