T1:数论。
<not_complete>
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 inline int in(){ 6 int x=0;bool f=0; char c; 7 for (;(c=getchar())<'0'||c>'9';f=c=='-'); 8 for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0'); 9 return f?-x:x; 10 } 11 int a[16],sum[3],n,m,ct=0,ans,res; 12 bool mk; 13 inline int gcd(int x,int y){ 14 return (!y)?x:gcd(y,x%y); 15 } 16 int main() 17 { 18 n=in();m=in();mk=0; 19 for (int i=1;i<=m;++i){ 20 a[ct]=in();if (a[ct]==1) {printf("0");return 0;} 21 if (!(a[ct]%3)) mk=(mk||a[ct]==3)?1:0,--ct;++ct; 22 }for (int i=0;i<3;++i) sum[i]=n/3; 23 if (n%3==1) ++sum[1]; 24 else if (n%3==2) ++sum[1],++sum[2]; 25 for (int i=1;i<(1<<ct);++i){ 26 int cnt=0,res=1,tmp; 27 for (int j=0;j<ct;++j)if (i&(1<<j)){ 28 if (1ll*res*a[j]/gcd(res,a[j])>1ll*n) {res=-1;break;} 29 res=a[j]/gcd(res,a[j])*res;++cnt; 30 }if (res==-1) continue; 31 tmp=n/res,cnt=(cnt&1)?-1:1; 32 for (int i=0;i<3;++i) sum[i]+=cnt*(tmp/3); 33 if (res%3==1){ 34 if (tmp%3==1) sum[1]+=cnt; 35 else if (tmp%3==2) sum[1]+=cnt,sum[2]+=cnt; 36 }else if (res%3==2){ 37 if (tmp%3==1) sum[2]+=cnt; 38 else if (tmp%3==2) sum[2]+=cnt,sum[1]+=cnt; 39 } 40 }ans=((sum[1]<sum[2])?sum[2]:sum[1]); 41 printf("%d",(mk||(n<3))?ans:ans+1);return 0; 42 }
T2:最大权闭合子图问题，转二分图匹配解决。
可以发现有冲突的格子(x,y)之间，(x+y)的奇偶性一定不同。
考虑将图黑白染色，每个黑色位置向该位置上的马能够控制的格子连边。
对于负权，可以发现不选一定更优，所以可以直接连权值为0的边，即对0取max。
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #define ME 220005 6 #define MN 20005 7 #define inf 0x7fffffff 8 using namespace std; 9 inline int in(){ 10 int x=0;bool f=0; char c; 11 for (;(c=getchar())<'0'||c>'9';f=c=='-'); 12 for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0'); 13 return f?-x:x; 14 } 15 struct edge{ 16 int to,next,cap; 17 }e[ME]; 18 const int dx[8]={-2,-1,1,2,2,1,-1,-2}; 19 const int dy[8]={1,2,2,1,-1,-2,-2,-1}; 20 int v[MN],head[MN],iter[MN],lev[MN]; 21 int cnt=1,n,m,s,t,sum; 22 inline void ins(int x,int y,int cp){ 23 e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;e[cnt].cap=cp; 24 e[++cnt].to=x;e[cnt].next=head[y];head[y]=cnt;e[cnt].cap=0; 25 } 26 inline void bfs(){ 27 queue<int> q;memset(lev,-1,sizeof(lev)); 28 lev[s]=0;q.push(s);while(!q.empty()){ 29 int u=q.front();q.pop(); 30 for (int i=head[u];i;i=e[i].next){ 31 int v=e[i].to; 32 if (lev[v]==-1&&e[i].cap>0) lev[v]=lev[u]+1,q.push(v); 33 } 34 } 35 } 36 inline int dfs(int u,int f){ 37 if (u==t) return f;int used=0; 38 for (int &i=iter[u];i;i=e[i].next){ 39 int v=e[i].to; 40 if (e[i].cap>0&&lev[u]<lev[v]){ 41 int w=dfs(v,min(f-used,e[i].cap)); 42 if (w>0){ 43 e[i].cap-=w;e[i^1].cap+=w;used+=w; 44 if (used==f) return f; 45 } 46 } 47 }return used; 48 } 49 inline int dinic(){ 50 int fl=0;while (1){ 51 bfs();if (lev[t]==-1) return fl; 52 memcpy(iter,head,sizeof(head)); 53 int d;while((d=dfs(s,inf))>0) fl+=d; 54 } 55 } 56 inline bool check(int x,int y){ 57 return ((x>=0)&&(x<n)&&(y>0)&&(y<=m)); 58 } 59 int main() 60 { 61 n=in();m=in();s=0;t=n*m+1; 62 for (int i=0;i<n;++i) 63 for (int j=1;j<=m;++j){ 64 v[i*m+j]=in(),sum+=max(0,v[i*m+j]); 65 if ((i+j)&1) ins(s,i*m+j,max(0,v[i*m+j])); 66 else ins(i*m+j,t,max(0,v[i*m+j])); 67 }for (int i=0;i<n;++i) 68 for (int j=1;j<=m;++j){ 69 if (!((i+j)&1)) continue; 70 for (int k=0;k<8;++k){ 71 int x=i+dx[k],y=j+dy[k]; 72 if (check(x,y)) ins(i*m+j,x*m+y,inf); 73 } 74 }printf("%d",sum-dinic());return 0; 75 }