A. Cow and Haybales
【题意】
给出一个长度为n的数列,每次操作可以将相邻的两个数字,其中一个-1,另外一个+1。
问K次操作后1位置的数最大为多少。
【思路】
直接把操作转化为对与第i个位置,花费的步数向1号位置转移个1。最后1号位置的最大值。
贪心的从左往右考虑,每次可以转移的1的个数为,now是当前剩余的步数。
【代码】
#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 110; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } int a[N]; int main() { int T = read(); while(T--) { int n = read(),d = read(); for(int i = 1;i <= n;++i) { a[i] = read(); if(i == 1) continue; int k = min(d / (i - 1),a[i]); d -= k * (i - 1); a[1] += k; } printf("%d\n",a[1]); } return 0; }
B. Cow and Friend
【题意】
给出n个喜欢的距离,每次可以移动一个喜欢的距离(欧几里得距离),问从走到最少需要多少步。
【思路】
特判为喜欢的距离的情况。
每次走最大的距离为最优方案。因为用mx走两步可以走出中的任何一个距离。
所以输出即可。
对于的情况,在排除上面特判的情况下,走一步肯定是不行的,所以也要特判输出2
【代码】
#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } void solve() { ll mx = 0,n = read(),X = read(); int flag = 0; for(int i = 1;i <= n;++i) { ll x = read(); mx = max(mx,x); if(x == X) flag = 1; } if(flag) {puts("1");return;} if(mx > X) puts("2"); else printf("%I64d\n",(mx + X - 1) / mx); } int main() { int T = read(); while(T--) { solve(); } return 0; }
C. Cow and Message
【题意】
给出一个长度为n的字符串,可以选择一个下标集合,使得S中的数字为等差数列。问所有可能的S所对应的字符串中,出现次数最多的那个出现了多少次。
【思路】
脑筋急转弯,题面具有很大迷惑性。
其实选择最优情况肯定满足或者。枚举这两个或一个字符,统计出现次数即可。
【代码】
#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 1000010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } char s[N]; ll ans[30][30],cnt[30]; int main() { scanf("%s",s + 1); int n = strlen(s + 1); for(int i = 1;i <= n;++i) { for(int j = 0;j < 26;++j) ans[s[i] - 'a'][j] += cnt[j]; cnt[s[i] - 'a']++; } ll anss = 0; for(int i = 0;i < 26;++i) { for(int j = 0;j < 26;++j) anss = max(anss,ans[i][j]); anss = max(anss,cnt[i]); } cout<<anss; return 0; }
D. Cow and Fields
【题意】
给出一个n个点m条边的无向图。边权均为1。再给出K个点,从这个K个点中选2两个连边,使得形成的图最短路最长。
【思路】
看到最短路最长容易误解为二分答案。
但稍微思考就会发现答案可定小于等于原图的最短路。
考虑的做法,枚举两个点,然后在之间连边。算出
表示从到的最短路。
所以求一下从1到每个点的最短路dis1,和从n到每个点的最短路dis2。
然后找到dis1和dis2的最大值相加???
显然不行,因为无法排除自己加自己的情况,而且无法解决做法中min起到的作用。
这里要用到类似与"国王游戏"中的贪心方法(拟阵)。
如果dis1[u]+dis2[v] < dis2[u] + dis1[v]说明u选dis1更小,就按照这个方式排个序。
然后从左向右枚举,左边的选dis1,右边的选dis2,统计即可。
【代码】
#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 200010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int v,nxt; }e[N << 1]; int a[N],head[N],ejs; void add(int u,int v) { e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs; } queue<int>q; void bfs(int S,int *dis) { q.push(S); while(!q.empty()) { int u = q.front();q.pop(); for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(!dis[v] && v != S) { dis[v] = dis[u] + 1; q.push(v); } } } } int dis1[N],dis2[N]; bool cmp(int x,int y) { return dis1[x] + dis2[y] < dis2[x] + dis1[y]; } int main() { int n = read(),m = read(),K = read(); for(int i = 1;i <= K;++i) a[i] = read(); for(int i = 1;i <= m;++i) { int u = read(),v = read(); add(u,v);add(v,u); } bfs(1,dis1); int ans = dis1[n]; bfs(n,dis2); sort(a + 1,a + K + 1,cmp); int now = dis1[a[1]],tmp = 0; for(int i = 2;i <= K;++i) { int x = a[i]; tmp = max(tmp,dis2[x] + now + 1); now = max(now,dis1[x]); } now = dis2[a[K]]; for(int i = K - 1;i >= 1;--i) { int x = a[i]; tmp = max(tmp,dis1[x] + now + 1); now = max(now,dis2[x]); } ans = min(ans,tmp); printf("%d\n",ans); return 0; }