比赛时候只做出AB，E题一眼看过去似乎线段树能搞，但是写完过不了样例，才发现看错题了，然后比赛就没啥时间了~~整体状况还是很糟糕，A，B题实在出得太慢，然后持续到现在还没出过C题。。。不能更弱%>_<%
A：在N*N的棋盘上放棋子，使得每一个棋子四周都没有相邻的棋子，问最多能够放置多少棋子。
这个直接每个格子一次判断能不能放就好
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
#define MAXN 1005
bool visit[MAXN][MAXN];
int main()
{
int n,cnt=0;
memset(visit,false,sizeof(visit));
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(!visit[i][j-1]&&!visit[i-1][j])
{
visit[i][j]=true;
cnt++;
}
}
}
printf("%d\n",cnt);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(visit[i][j])
{
printf("C");
}
else
{
printf(".");
}
}
printf("\n");
}
return 0;
}
B:读懂题就很好搞了，并且是special judge，没什么技术含量。。。代码写得很挫
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
#define MAXN 1005
bool visit[MAXN][MAXN];
struct node
{
int x,y;
};
node pr[MAXN];
int a[MAXN][MAXN];
int main()
{
int cnt,n,m,p;
memset(visit,false,sizeof(visit));
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
}
cnt=0;
if(p==0)
{
for(int i=1;i<m;i++)
for(int j=i+1;j<=m;j++)
for(int k=1;k<=n;k++)
if(a[k][i]>a[k][j])
{
swap(a[k][i],a[k][j]);
if(!visit[i][j])
{
visit[i][j]=true;
pr[cnt].x=i;
pr[cnt++].y=j;
}
}
}
else
{
for(int i=1;i<m;i++)
for(int j=i+1;j<=m;j++)
for(int k=1;k<=n;k++)
if(a[k][i]<a[k][j])
{
swap(a[k][i],a[k][j]);
if(!visit[i][j])
{
visit[i][j]=true;
pr[cnt].x=j;
pr[cnt++].y=i;
}
}
}
printf("%d\n",cnt);
for(int i=0;i<cnt;i++) printf("%d %d\n",pr[i].x,pr[i].y);
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) printf("%d ",a[i][j]);
printf("\n");
}*/
return 0;
}
C：有n头牛排在一行，每头牛要么朝左，要么朝右，需要按一定顺序对所有的牛进行挤奶，对于当前挤奶的牛，其他能够看到它的未挤奶的牛的奶量会减少1，问最少会减少多少牛奶？
这个可以贪心搞，统计每头奶牛能被多少条其他的牛看到等于每头牛能看到的奶牛数，先对朝右的奶牛进行挤奶，然后逆序对朝左的奶牛进行挤奶。我们按顺序进行统计就好，如果当前的牛是面向左边，那么就累加它左边面朝右的奶牛数加到最终答案中，线性扫一遍就OK
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
int main()
{
int n;
LL cnt=0,ans=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int a;
scanf("%d",&a);
if(a) cnt++;
else ans+=cnt;
}
cout<<ans<<endl;
return 0;
}
D：有一个N*N(1 ≤ n ≤ 109)的网格，有m(1 ≤ m ≤ 105)个单位格子放置有障碍物，要求你从(1,1)走到(n,n),问最少的时间是多少（只能往下或者往右走）？
暂时木有想法~~
E：有一颗n个结点的有根树，每个结点有一个值a[i],可以对树进行以下两种操作:
1、"1 x val" 把结点x的值加val,同时把结点x的儿子的值加上-val,结点x的儿子的儿子加上val，等等依次这样进行
2、"2 x"查询结点x的值
由于第一个操作是对整个以x为根的子树进行修改，因此我们可以利用dfs序把整个子树重新编号为连续的区间，然后与结点x的树高的奇偶性相同的儿子结点是加val，否则就是加-val,一般我们我们遇到的区间操作都是，对某个区间进行同一种修改操作，但是此题是结点的奇偶性不同，操作不同，如果我们用一颗线段树或者树状数组的话搞起来很麻烦，我们可以根据结点的奇偶搞两颗BIT，然后根据结点x的奇偶性对对应的BIT进行相应的区间修改操作，查询也是根据结点的奇偶性在对应的BIT上进行查询
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 200055
int a[MAXN];
typedef struct
{
int adv;
int next;
} NODE;
NODE edg[2*MAXN];
int head[MAXN],c[2][MAXN];
int low[MAXN],high[MAXN],deg[MAXN];
bool visit[MAXN];
int n,m,k,step=0;
void addege(int u,int v)
{
edg[k].adv=v;
edg[k].next=head[u];
head[u]=k++;
}
void dfs(int u,int dg)
{
int i;
low[u]=++step;
deg[u]=dg;
visit[u]=true;
for(i=head[u]; i!=-1; i=edg[i].next)
if(!visit[edg[i].adv])
dfs(edg[i].adv,(dg+1)%2);
high[u]=step;
}
int lowbit(int x)
{
return x&-x;
}
void add(int x,int d,int fg)
{
while(x<=n)
{
c[fg][x]+=d;
x+=lowbit(x);
}
}
int query(int x,int fg)
{
int ret=0;
while(x>0)
{
ret+=c[fg][x];
x-=lowbit(x);
}
return ret;
}
int main(void)
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
k=1;
for(int i=1; i<n; i++)
{
int u,v;
scanf("%d%d",&u,&v);
addege(u,v);
}
dfs(1,0);
while(m--)
{
int op,x,v;
scanf("%d%d",&op,&x);
if(op==1)
{
scanf("%d",&v);
add(low[x],v,deg[x]);
add(high[x]+1,-v,deg[x]);
add(low[x],-v,(deg[x]+1)%2);
add(high[x]+1,v,(deg[x]+1)%2);
}
else
printf("%d\n",a[x]+query(low[x],deg[x]));
}
return 0;
}