19:10~21:10 CQOI2014 Day1
这一场比较简单...
和谐矩阵和数三角形都比较好做 大概是提高组难度的吧
危桥是一个明显的网络流题 但是由于我太naive了没有想到怎么建图所以就没有得分
和谐矩阵
题解:
高斯消元解异或方程组
首先列出n*m个异或方程 就是每个格子列一个然后消元 得到一个下三角矩阵
就是类似这样
*00000
**0000
***000
****00
*****0
(手动六个*)(打不出来)
然后显然的 全是0是一组解
然后就要找自由元 从1到n*m顺着找
如果a[i][i]==0那么这是一个自由元 把它赋成1
否则根据前面的几项算出当前的值
如果一个自由元都没有那就只能全是0(所以不会存在这种情况)
然后就结束了
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int dx[]={1,0,-1,0,0},dy[]={0,1,0,-1,0};
int n,m;
int a[2000][2000];
int b[50][50],cnt;
int ans[2000];
int main(){
#ifdef LZT
freopen("in","r",stdin);
#endif
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
b[i][j]=++cnt;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int d=0;d<=4;d++){
int nwx=i+dx[d],nwy=j+dy[d];
if(nwx>=1 && nwx<=n && nwy>=1 && nwy<=m) a[b[i][j]][b[nwx][nwy]]=1;
}
for(int i=cnt;i>=1;i--){
int k=-1;
for(int j=1;j<=i;j++)
if(a[j][i]) k=j;
if(k==-1) continue;
if(k!=i){
for(int j=1;j<=cnt;j++)
swap(a[i][j],a[k][j]);
}
for(int x=1;x<i;x++)
if(a[x][i]){
for(int j=1;j<=i;j++)
a[x][j]^=a[i][j];
}
}
for(int i=1;i<=cnt;i++){
if(a[i][i]==0){
ans[i]=1;
continue;
}
for(int j=1;j<i;j++)
if(a[i][j]) ans[i]^=ans[j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
b[i][j]=ans[b[i][j]];
/*
for(int i=1;i<=cnt;i++){
for(int j=1;j<=cnt;j++)
printf("%d ",a[i][j]);
puts("");
}
*/
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
printf("%d ",b[i][j]);
puts("");
}
return 0;
}
Review:
没什么难的地方...
数三角形
题解:
这道题还是很有意思的
不难看出应该用总数-三点共线的数量
那么三点共线的数量怎么求呢?
我首先想把三个点的坐标设出来算一算 发现没什么用
于是考虑斜率
但是会发现同一个斜率的线段有长有短 不好算
于是(看了题解之后发现) 我们只要考虑从左上角出发的所有线段即可
对于这样的一条线段(0,0)->(x,y) 在线段上的整点个数(不包括两端)为gcd(x,y)-1 这条线段出现的次数为向右平移的次数*向下平移的次数就是(m-y+1)*(n-x+1) 所以这条线段的贡献就是前面两个的积 因为不仅有左上->右下的还有右上->坐下的 所以乘2
横的和竖的单独算 加起来就好了
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
ll n,m;
int main(){
#ifdef LZT
freopen("in","r",stdin);
#endif
n=read(),m=read();
ll sum=(n+1)*(m+1);
ll ans=sum*(sum-1)/2*(sum-2)/3;
if(n>=2) ans=ans-(n+1)*n/2*(n-1)/3*(m+1);
if(m>=2) ans=ans-(m+1)*m/2*(m-1)/3*(n+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=ans-(__gcd(i,j)-1)*(n-i+1)*(m-j+1)*2;
printf("%lld\n",ans);
return 0;
}
Review:
想到斜率之后瞎想了一大堆但事实上处理很简单也很巧妙
思维要简单一些 太复杂的想法尽量不要去碰
危桥
边很好想
就是如果是普通边就连一条+∞的边 如果是危桥就连一条容量为2的边
但是如果直接这样跑网络流判断是否满流会出问题 a1不能完全和b1对应 就是可能出现a1流到b2中一些 a2流到b1中一些 然后还是满流的情况
想了一会 无果 于是就要靠题解啦
就是先这样跑一次 然后把a2放到汇点那边去 b2放到源点那边去 相当于a2和b2交换 再跑一次 如果都是满流 那么OK
至于为什么是对的... 某博客是这么写的
但是我画图怎么就理解不出来呢...
大概就是这样的
我们需要这样
但是事实上不能做到
问题出在可能会变成这样
红线就是出问题的地方
那么我们交换了a2,b2之后变成这样
这时候红线就无法对答案产生贡献
所以就可以了
那有人说会不会是这样
但由于dinic增广的时候要满足d[e.to]=d[nw]+1 所以a1 不可能走到a2
所以这是不存在的
于是这题就做完了
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
char get(){
char c=getchar();
while(c!='O' && c!='N' && c!='X') c=getchar();
return c;
}
const int inf=1e9;
int n,a1,a2,an,b1,b2,bn;
char s[100][100];
struct Edge{
int fr,tt,cap,flow;
};
struct Dinic{
int m,s,t;
vector<Edge> edges;
vector<int> adj[200];
int cur[200],d[200];
bool vis[200];
void clear(){
edges.clear();
m=0;
for(int i=0;i<100;i++)
adj[i].clear();
}
void addedge(int a,int b,int f){
edges.push_back((Edge){a,b,f,0});
edges.push_back((Edge){b,a,f,0});
m=edges.size();
adj[a].push_back(m-2);
adj[b].push_back(m-1);
}
void addedge2(int a,int b,int f){
edges.push_back((Edge){a,b,f,0});
edges.push_back((Edge){b,a,0,0});
m=edges.size();
adj[a].push_back(m-2);
adj[b].push_back(m-1);
}
bool BFS(){
memset(vis,0,sizeof(vis));
queue<int> Q;
Q.push(s);
d[s]=0;
vis[s]=1;
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int _=0;_<adj[u].size();_++){
Edge &e=edges[adj[u][_]];
if(!vis[e.tt] && e.cap>e.flow){
vis[e.tt]=1;
d[e.tt]=d[u]+1;
Q.push(e.tt);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x==t || a==0) return a;
int flow=0,f;
for(int &_=cur[x];_<adj[x].size();_++){
Edge &e=edges[adj[x][_]];
if(d[e.tt]==d[x]+1 && (f=DFS(e.tt,min(a,e.cap-e.flow)))>0){
flow+=f;
e.flow+=f;
edges[adj[x][_]^1].flow-=f;
a-=f;
if(a==0) break;
}
}
return flow;
}
int calc(int s,int t){
this->s=s;this->t=t;
int ans=0;
while(BFS()){
memset(cur,0,sizeof(cur));
ans=ans+DFS(s,inf);
}
return ans;
}
} gr;
int main(){
#ifdef LZT
freopen("in","r",stdin);
#endif
while(scanf("%d",&n)==1){
a1=read(),a2=read(),an=read(),b1=read(),b2=read(),bn=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
s[i][j]=get();
a1++;
a2++;
b1++;
b2++;
gr.clear();
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
if(s[i][j]=='O') gr.addedge(i,j,2);
else if(s[i][j]=='N') gr.addedge(i,j,1000000);
}
int ss=n+1,t=n+2;
gr.addedge2(ss,a1,2*an);
gr.addedge2(ss,b1,2*bn);
gr.addedge2(a2,t,2*an);
gr.addedge2(b2,t,2*bn);
int ans1=gr.calc(ss,t);
gr.clear();
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
if(s[i][j]=='O') gr.addedge(i,j,2);
else if(s[i][j]=='N') gr.addedge(i,j,1000000);
}
gr.addedge2(ss,a1,2*an);
gr.addedge2(ss,b2,2*bn);
gr.addedge2(a2,t,2*an);
gr.addedge2(b1,t,2*bn);
int ans2=gr.calc(ss,t);
if(ans1==ans2 && ans1==2*(an+bn))
puts("Yes");
else
puts("No");
}
return 0;
}
/*
4 0 1 1 2 3 1
XOXX
OXOX
XOXO
XXOX
4 0 2 1 1 3 2
XNXO
NXOX
XOXO
OXOX
*/
Review:
1.注意做第二次网络流的时候要改几条边
我一开始想在原图上改以节省时间
但是我只改动了edges里面的边 没改adj中的对应的序号
一直wa 调了很长时间才发现问题
最后还是改成了重新建图
2.遇到起点与终点之间有对应关系的时候可以考虑把每一组的起点终点都反过来再求一遍 O(2^(n-1))来判断是否可行
