锐客网

  1. 首页 > it技术 > >

2019 GDUT Rating Contest #II 这是群题解，七篇！！！

题解

2019 GDUT Rating Contest #II 这是群题解，七篇！！！ 题目见：http://codeforces.com/group/NVaJtLaLjS/contest/238194 原谅一下，一片一片写太累了有辱师兄的高效教诲 A：没想到吧，我先放代码，哈哈哈。

#include #include #include using namespace std; int st[16][10108]; int er[16]; int maxim(int x,int y) { int t=int(log(double(y-x+1))/log(double(2))); return max(st[t][x],st[t][y-er[t]+1]); } int main() { int i,j,n,k; int f[10010]; int dp[10010]; scanf("%d %d",&n,&k); for (i=1; i<=n; i++) scanf("%d",&f[i]); er[0]=1; for (i=1; i<=15; i++) er[i]=er[i-1]*2; for (i=1; i<=n; i++) st[0][i]=f[i]; for (i=1; i<=int(log(double(n))/log(double(2)))+1; i++) for (j=1; j<=n; j++) if (j+er[i]-1<=n) st[i][j]=max(st[i-1][j],st[i-1][j+er[i-1]]); for (i=0; i<=10000; i++) dp[i]=0; dp[1]=f[1]; for (i=2; i<=n; i++) for (j=i; j>=max(1,i-k+1); j--) { dp[i]=max(dp[i],dp[j-1]+(i-j+1)*maxim(j,i)); } printf("%d\n",dp[n]); return 0; }

我的做法是: 可以将确定的区间标记为1000000…不确定标记为-1，如果出现矛盾，那就直接输出-1.
B：
#include #include #include #include #include using namespace std; int main() { int n,i,j; double ans=0; int f[105]; int a[105]; int q[105]; scanf("%d",&n); for (i=1; i<=n; i++) scanf("%d",&a[i]); sort(a+1,a+n+1); for (i=1; i<=100; i++) q[i]=0; for (i=1; i<=n; i++) { if (i==1) f[i]=2; else if (i==n) f[i]=n-1; else { if (a[i+1]-a[i]>=a[i]-a[i-1]) f[i]=i-1; else f[i]=i+1; } } for (i=1; i<=n; i++) { if (i==1) f[i]=2; else if (i==n) f[i]=n-1; else { if (a[i+1]-a[i]>=a[i]-a[i-1]) f[i]=i-1; else f[i]=i+1; } } for (i=1; i<=n; i++) { q[f[i]]++; } for (i=1; i<=n; i++) { if (f[f[i]]==i&&q[f[i]]==1&&q[i]==1) ans+=0.5; } for (i=1; i<=n; i++) if (q[i]==0) ans++; //for (i=1; i<=n; i++) printf("%d %d\n",f[i],q[i]); printf("%d\n",int (ans) ); return 0; }

我的做法是: 【2019 GDUT Rating Contest #II 这是群题解，七篇！！！】通过伟大的师兄教的拓扑排序，找到入度为0的起始边，这就表示只要在这些起始地方放一个球就可以传到其他地方了，不过还要特判一手二人转：两头牛自顾自互相传组成环，这种情况只要找到入度为1且他传下去的下一个传给自己就ok了。
C：这题让我想起当时corn邓拿来坑我们渣渣的题
#include #include #include #include #includeusing namespace std; int main() { int i,j,n,l,last=0; int tf,tb; int d[100005],c[100005]; int q[100005]; scanf("%d %d %d %d",&l,&n,&tf,&tb); d[0]=0; c[0]=0; int tail=1; q[0]=0; for (i=1; i<=n; i++) {scanf("%d %d",&d[i],&c[i]); while (c[q[tail]]<=c[i]&&tail>1) { if (tail>=10&&c[q[tail/2]]<=c[i]) tail/=2; tail--; }q[tail+1]=i; tail++; } long long ans=0; for (i=1; i<=tail; i++) { long long ci=c[q[i]],di=d[q[i]]-d[q[i-1]],t=(tf-tb); ans+=ci*di*t; } printf("%I64d\n",ans); return 0; }

我的做法是: 简单的贪心加dp，直接优先取最大的当前状态进行状态转移。
D和E：这题我没做出来，但是有大佬呀： 参拜链接：https://blog.csdn.net/wen_yongqi/article/list/4?t=1&
C：这题让我想起当时corn邓拿来坑我们渣渣的题
#include #include #include #include #include using namespace std; int main() { int x,y,a,b; scanf("%d %d %d %d",&x,&y,&a,&b); printf("%d",min(abs(y-x),min(abs(x-a)+abs(y-b),abs(x-b)+abs(y-a)))); return 0; }

我的做法是: 我只想说：模拟就完事了，呸！什么模拟，两个式子搞定有没有。
G：炫耀一下，比赛时只有本题只有我一人独a了，啊啊啊我知道错了，师兄大佬别来打我呀！！！
#include #include #include #include #include using namespace std; int main() { int i,j,n,m,b,c,t; int a[255]; int d[255]; int s[255]; int f[255][255]; d[0]=0; s[0]=0; scanf("%d %d",&n,&b); for (i=1; i<=n; i++) scanf("%d",&a[i]); for (i=1; i<=b; i++) scanf("%d %d",&d[i],&s[i]); for (i=0; i<=252; i++) for (j=0; j<=252; j++) f[i][j]=n+1; f[0][0]=0; for (i=0; i<=b; i++) for (j=0; j<=n-1; j++) { if (f[i][j]

我的做法是: 这只是一道基本的dp题，我碰巧先看到了它，其他大佬们估计都在沉迷DE题里。相遇的瞬间，我立刻识别了它是dp。于是状态转移见上代码。

    推荐阅读


    上一篇：# 2019 GDUT Rating Contest #I H. Mixing Milk

    下一篇：每天聊本书第二十八天《像间谍一样思考》