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;
}
题目大意：给你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
*/
1 second
256 megabytes
standard input
standard output
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
*/
题目大意：一个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不知怎样下手。