首页 > 代码库 > Codeforces #245(div2)
Codeforces #245(div2)
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("\n");
}
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
*/
Iahub is very proud of his recent discovery, propagating trees. Right now, he invented a new tree, called xor-tree. After this new revolutionary discovery, he invented a game for kids which uses xor-trees.
The game is played on a tree having n nodes, numbered from 1 to n. Each node i has an initial value initi, which is either 0 or 1. The root of the tree is node 1.
One can perform several (possibly, zero) operations on the tree during the game. The only available type of operation is to pick a nodex. Right after someone has picked node x, the value of node x flips, the values of sons of x remain the same, the values of sons of sons of x flips, the values of sons of sons of sons of x remain the same and so on.
The goal of the game is to get each node i to have value goali, which can also be only 0 or 1. You need to reach the goal of the game by using minimum number of operations.
The first line contains an integer n (1?≤?n?≤?105). Each of the next n?-?1 lines contains two integers ui and vi (1?≤?ui,?vi?≤?n; ui?≠?vi) meaning there is an edge between nodes ui and vi.
The next line contains n integer numbers, the i-th of them corresponds to initi (initi is either 0 or 1). The following line also contains ninteger numbers, the i-th number corresponds to goali (goali is either 0 or 1).
In the first line output an integer number cnt, representing the minimal number of operations you perform. Each of the next cnt lines should contain an integer xi, representing that you pick a node xi.
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
2 4 7
题目大意：给你一颗树，给你所有节点的初始状态，然后再给你一个需要转变到的状态，如果一个节点的状态发生改变，那么他的儿子节点不变^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
*/
D：D. Working out
题目大意：一个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\n",res);
}
return 0;
}
/*
3 3
100 100 100
100 1 100
100 100 100
*/
E题，DFS不知如何下手。