「CF545X」Codeforces Round #303 (Div. 2)
A. Toy Cars
模拟
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int a[105][105]; int main() { n=read(); vector<int>ans; for(int i=1;i<=n;i++) { bool flag=0; for(int j=1;j<=n;j++) { a[i][j]=read(); if(a[i][j]==1||a[i][j]==3)flag=1; } if(!flag)ans.push_back(i); } printf("%lu\n",ans.size()); for(int i=0;i<ans.size();i++) printf("%d ",ans[i]); return 0; } |
B. Equidistant String
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,tot; char a[100005],b[100005]; int main() { scanf("%s%s",a+1,b+1); n=strlen(a+1); for(int i=1;i<=n;i++) if(a[i]!=b[i])tot++; if(tot&1)puts("impossible"); else { int t=0; for(int i=1;i<=n;i++) if(a[i]!=b[i]) { if(t<tot/2)t++,printf("%c",a[i]); else printf("%c",b[i]); } else printf("%c",a[i]); } return 0; } |
C. Woodcutters
给n棵树在一维数轴上的坐标,以及它们的高度。现在要你砍倒这些树,树可以向左倒也可以向右倒,砍倒的树不能重合、当然也不能覆盖其他的树原来的位置,现在求最大可以砍倒的树的数目。
题解
第一棵树的左边和最后一棵树的右边没树,所以他们向两边倒,然后对于中间的树来说,首先先向左边倒,然后左边距离如果不够的话再向右边倒。
当然也可以dp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int x[100005],h[100005]; int main() { n=read(); if(n==1) { puts("1"); return 0; } for(int i=1;i<=n;i++) x[i]=read(),h[i]=read(); int ans=2; for(int i=2;i<=n-1;i++) if(abs(x[i]-x[i-1])>h[i])ans++; else if(abs(x[i]-x[i+1])>h[i]) ans++,x[i]+=h[i]; printf("%d\n",ans); return 0; } |
D. Queue
显然t小的放在前面考虑,依次贪心
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,ans; int t[100005]; int main() { n=read(); for(int i=1;i<=n;i++)t[i]=read(); sort(t+1,t+n+1); ll tot=0; for(int i=1;i<=n;i++) if(tot<=t[i])tot+=t[i],ans++; printf("%d\n",ans); return 0; } |
E. Paths and Trees
求最短路径树,裸题QAQ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<ll,int> using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt=1; int last[300005],pre[300005]; bool mark[600005],vis[300005]; ll dis[300005]; struct edge{ int to,next,v; }e[600005]; void insert(int u,int v,int w) { e[++cnt]=(edge){v,last[u],w};last[u]=cnt; e[++cnt]=(edge){u,last[v],w};last[v]=cnt; } priority_queue<pa,vector<pa>,greater<pa> >q; void dijkstra(int x) { for(int i=1;i<=n;i++)dis[i]=1e60; dis[x]=0;q.push(make_pair(0,x)); while(!q.empty()) { int now=q.top().second;q.pop(); if(vis[now])continue;vis[now]=1; for(int i=last[now];i;i=e[i].next) if(!vis[e[i].to]&&dis[now]+e[i].v<=dis[e[i].to]) { if(dis[now]+e[i].v<dis[e[i].to])pre[e[i].to]=i; else if(e[i].v<e[pre[e[i].to]].v)pre[e[i].to]=i; dis[e[i].to]=dis[now]+e[i].v; q.push(make_pair(dis[e[i].to],e[i].to)); } } } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); insert(u,v,w); } int t=read(); dijkstra(t); for(int i=1;i<=n;i++) mark[pre[i]]=1; vector<int>ans; ll tot=0; for(int i=2;i<=cnt;i+=2) if(mark[i]||mark[i+1]) { ans.push_back(i/2); tot+=e[i].v; } printf("%I64d\n",tot); for(int i=0;i<ans.size();i++) printf("%d ",ans[i]); return 0; } |
请问黄学长……C题是怎么个策略贪心的哦……?