A:A. Points and Segments (easy)
题目看了n久,開始认为尼玛这是div2的题目么,题目还标明了easy。。
意思是给你一n个点,m个区间,在n个点上放蓝球或者红球,然后让你找一种选择方案使得m个区间内的蓝球和红球数量之差不超过1.
開始想过用dfs,只是这仅仅是div2的A题而已。。
然后想了下,直接输出010101序列不就能够么。
交了一发,发现要先排个序,再输出就能够了。
AC代码:
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int res[150]; struct node { int x,id; }nod[150]; bool cmp(node a,node b) { return a.x<b.x; } int main() { int i,n,m; int a,b; while(~scanf("%d%d",&n,&m)) { for(i=0;i<n;i++) scanf("%d",&nod[i].x),nod[i].id=i; for(i=0;i<m;i++) scanf("%d%d",&a,&b); sort(nod,nod+n,cmp); int t=0; for(i=0;i<n;i++) res[nod[i].id]=(++t)%2; printf("%d",res[0]); for(i=1;i<n;i++) printf(" %d",res[i]); printf(" "); } return 0; }
B:B. Balls Game
题目大意:给你n个球,然后最多k个种类,同类的挨在一起同类的超过三个的能够抵消。開始的n个没有抵消的情况,问给你一个颜色为x的球,问你用这个球insert进去最多能消掉n个球里面的个数。
直接模拟就好,只是,自己被自己坑了好久。。
AC代码:
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<algorithm> #define ll long long using namespace std; int a[105]; int main() { int n,k,x; int i; while(cin>>n>>k>>x) { int res=0; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) { int ans=0,t1,t2; if(a[i]==x&&i+1<=n&&a[i+1]==x) { ans+=2; t1=i-1,t2=i+2; while(t1>=1&&t2<=n) { int cnt=0; int x=a[t1]; while(a[t2]==x&&t2<=n) { cnt++; t2++; } while(a[t1]==x&&t1>=1) { cnt++; t1--; } if(cnt<3) break; else ans+=cnt; } res=max(res,ans); } } cout<<res<<endl; } return 0; } /* 10 2 2 2 2 1 1 2 2 1 1 2 2 */
题目大意:给你一颗树,给你全部节点的初始状态,然后再给你一个须要转变到的状态,假设一个节点的状态发生改变,那么他的儿子节点不变^0,他的儿子的儿子节点^1,他儿子的儿子的儿子。。找最小的次数。
直接从根,(题目说了根是1)往下dfs,就可以。
AC代码:
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<algorithm> #include<vector> using namespace std; const int maxn=100005; vector <int> mq[maxn]; int sta[maxn],en[maxn]; int res[maxn]; int cnt; void dfs(int cur,int fa,int u,int v) { int flag=0; sta[cur]^=v; if(sta[cur]!=en[cur]) { flag=1; res[cnt++]=cur; } v=flag^v; for(int i=0;i<mq[cur].size();i++) { int nex=mq[cur][i]; if(nex!=fa) { dfs(nex,cur,v,u); } } } int main() { int n,i; while(cin>>n) { cnt=0; int u,v; for(i=1;i<=n;i++) mq[i].clear(); for(i=1;i<n;i++) { cin>>u>>v; mq[u].push_back(v); mq[v].push_back(u); } for(i=1;i<=n;i++) cin>>sta[i]; for(i=1;i<=n;i++) cin>>en[i]; dfs(1,0,0,0); cout<<cnt<<endl; for(i=0;i<cnt;i++) cout<<res[i]<<endl; } return 0; } /* 10 2 1 3 1 4 2 5 1 6 2 7 5 8 6 9 8 10 5 1 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 1 */
题目大意:一个n*m的格子,一个人从(1,1)走到(n,m),一个人从(n,1)走到(1,m),他们速度不同,必须有一个交点,在那个交点那里的分数不算,其它两个人走过的格子分数都仅仅算一次,问最大得多少分。第一个人仅仅能往右下方向走,第二个人仅仅能往右上方向走。
解题思路:我们须要枚举他们的交点,然后判定情况。须要记录来的方向,dp,先四次dp预处理,然后找最大值。详见图片与代码。
能够思考下,仅仅有这两种情况,不然就会重叠,而重叠的仅仅算一次的。
AC代码:
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<algorithm> #define ll long long using namespace std; int dp[4][1005][1005]; int a[1005][1005]; int n,m; void solve() { int i,j; for(i=1; i<=n; i++) //左上 for(j=1; j<=m; j++) dp[0][i][j] = max(dp[0][i-1][j],dp[0][i][j-1]) + a[i][j]; for(i=1; i<=n; i++) //右上 for(j=m; j>=1; j--) dp[1][i][j] = max(dp[1][i-1][j],dp[1][i][j+1]) + a[i][j]; for(i=n; i>=1; i--) //左下 for(j=1; j<=m; j++) dp[2][i][j] = max(dp[2][i][j-1],dp[2][i+1][j]) + a[i][j]; for(i=n; i>=1; i--) //右下 for(j=m;j>=1; j--) dp[3][i][j] = max(dp[3][i][j+1],dp[3][i+1][j]) + a[i][j]; } int main() { int i,j; memset(dp,0,sizeof(dp)); while(cin>>n>>m) { for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&a[i][j]); solve(); int res = 0; for(i=2; i<n; i++) for(j=2; j<m; j++) { int t1,t2; t1=dp[0][i-1][j]+dp[3][i+1][j]+dp[1][i][j+1]+dp[2][i][j-1]; t2=dp[0][i][j-1]+dp[3][i][j+1]+dp[1][i-1][j]+dp[2][i+1][j]; //cout<<t1<<" "<<t2<<endl; res=max(res,max(t1,t2)); } printf("%d ",res); } return 0; } /* 3 3 100 100 100 100 1 100 100 100 100 */
E题,DFS不知怎样下手。