T1 fuction
题意:求给定a,b,c,求ax+by=c的正整数解个数
题解:扩展欧几里得求出最小正整数解,然后通过 <nobr> x=x0−k×bgcd(a,b) </nobr>, <nobr> y=y0+k×agcd(a,b) </nobr>得到解的数目,外加各种瞎搞特判
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a,b,c,G,x,y,ans,k;
int exgcd(int a,int b,int &x,int &y)
{
if(!b) {x=1,y=0;return a;}
int tmp=exgcd(b,a%b,x,y);
int xx=x;
x=y;
y=xx-a/b*y;
return tmp;
}
int main()
{
freopen("fuction.in","r",stdin);
freopen("fuction.out","w",stdout);
int T=0;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&a,&b,&c);
if(a+b==c){cout<<1<<endl;continue;}
if(a==0&&b==0) {if(c!=0) cout<<0<<endl;else printf("ZenMeZheMeDuo\n");continue;}
if(a==0){if(c%b||c/b<=0) cout<<0<<endl;else printf("ZenMeZheMeDuo\n");continue;}
if(b==0){if(c%a||c/a<=0) cout<<0<<endl;else printf("ZenMeZheMeDuo\n");continue;}
if(a<0&&b<0) a=-a,b=-b,c=-c;
x=y=0;
G=exgcd(a,b,x,y);
if(c%G){printf("0\n");continue;}
x*=c/G,y*=c/G;
if(a*b<0){printf("ZenMeZheMeDuo\n");continue;}//a,b开long long比较稳
k=b/G;
x=(x%k+k)%k;if(!x) x+=abs(k);
y=(c-a*x)/b;
if(b/G>0)
{
if(y>0) ans=y/(a/G)+(y%(a/G)!=0);
if(y<=0) ans=0;
}
if(b/G<0)
{
if(y>0) ans=y/(-a/G)+(y%(-a/G)!=0);
if(y<=0) ans=0;
}
if(ans>65535) printf("ZenMeZheMeDuo\n");
else printf("%d\n",ans);
}
return 0;
}
T2 coloration
树型DP,用 <nobr> f[i][j] </nobr>表示以i为跟的子树中有j个黑色点时的最大权值
DP方程 <nobr> f[u][j]=max(f[u][j−k]+f[v][k]+w×(k×(m−k)+(size[v]−k)×((n−m)−(size[v]−k)))) </nobr>
只要考虑到每走过一条边,对于最终答案的贡献是:边权 <nobr> × </nobr>(走过的黑色点 <nobr> × </nobr>未走过的黑色点+走过的白色点 <nobr> × </nobr>未走过的白色点),然后就很好转移了
实现的时候注意循环的边界和枚举顺序
//by sdfzchy
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int N=2010;
int n,m,ecnt,fa[N],head[N],size[N];
LL f[N][N];//表示以i为根的子树,有j个黑点时的最大权值
struct edge
{
int v,w,nxt;
}e[N<<1];
void add(int u,int v,int w)
{
e[++ecnt].nxt=head[u];
e[ecnt].v=v;
e[ecnt].w=w;
head[u]=ecnt;
}
void dfs(int u)
{
size[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v!=fa[u])
{
fa[v]=u;
dfs(v);
size[u]+=size[v];
for(int j=min(size[u],m);j>=0;j--)
for(int k=max(0,j-(size[u]-size[v]));k<=min(size[v],j);k++)
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]+1ll*e[i].w*(k*(m-k)+(size[v]-k)*((n-m)-(size[v]-k))));
}
}
}
int main()
{
freopen("coloration.in","r",stdin);
freopen("coloration.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1,u,v,w;i<=n-1;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
fa[1]=1;
dfs(1);
printf("%lld\n",f[1][m]);
return 0;
}
T3 ray
60分可以爆搜
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
bool vis[1010][1010][5],used[1010][1010];
int ans,n,m,k,x,y,xx,yy;
char s[2];
int c(int xx,int yy)
{
if(xx==1&&yy==1) return 1;
if(xx==1&&yy==-1) return 2;
if(xx==-1&&yy==1) return 3;
if(xx==-1&&yy==-1) return 4;
}
int tot;
void dfs(int x,int y,int xx,int yy)
{
if(vis[x][y][c(xx,yy)]) return;
if(!vis[x][y][0]) ans++,vis[x][y][0]=vis[x][y][c(xx,yy)]=1;
int nx=x+xx,ny=y+yy;
if(!used[nx][ny]) dfs(nx,ny,xx,yy);
else
{
if(!used[nx][y]&&used[x][ny]) dfs(nx,y,xx,-yy);
else if(used[nx][y]&&!used[x][ny]) dfs(x,ny,-xx,yy);
else dfs(x,y,-xx,-yy);
}
}
int main()
{
freopen("ray.in","r",stdin);
freopen("ray.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
used[x][y]=1;
}
char aa,bb;
int xx,yy;
scanf("%d%d",&x,&y);
scanf("%s",s);
for(int i=0;i<=n+1;i++)
{
used[i][0]=1;
used[i][m+1]=1;
}
for(int i=0;i<=m+1;i++)
{
used[0][i]=1;
used[n+1][i]=1;
}
xx=(s[1]=='E')?1:-1;
yy=(s[0]=='S')?1:-1;
if(n<=1000)
{
dfs(x,y,xx,yy);
printf("%d\n",ans);
}
else printf("1\n");
return 0;
}
正解 同codeforces274E
可以证明反射的次数是 <nobr> O(n+m+k) </nobr>级别的
因为光路一定是循环的,即从一个位置出发一定会回到这个地方,所以光线可以分为左对角线和右对角线,可以用一个二元组 <nobr> (x±y,x) </nobr>来描述一个障碍点,用pair存在一个vector中,那么我们每次模拟光路时,就可以 <nobr> O(logk) </nobr>地二分查找可能遇到的障碍点,复杂度大约是 <nobr> O((n+m+k)logk) </nobr>
//by sdfzchy
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define LL long long
#define ALL(x) (x).begin(),(x).end()
using namespace std;
int n,m,k,x,y,xx,yy;
typedef pair<int,int> node;
vector<node> seg[2];
char s[2];
LL ans;
bool flag;
void add(int tx,int ty)
{
seg[0].push_back(node(tx-ty,tx));
seg[1].push_back(node(tx+ty,tx));
}
void reflect()
{
int d=(xx!=yy);
node p=d?node(x+y,x):node(x-y,x);
vector<node>::iterator it=upper_bound(ALL(seg[d]),p);
while(it->first!=p.first) it--;
if(xx<0) while(it->second >= x ) it--;
ans+=abs(x-it->second)-1;
x=it->second;
y=d?(it->first - x):(x-it->first);
bool A=binary_search(ALL(seg[0]),node(x-y-xx,x-xx));
bool B=binary_search(ALL(seg[0]),node(x-y+yy,x));
if(A==B) flag=1,xx=-xx,yy=-yy;
else if(A) x-=xx,yy=-yy;
else if(B) y-=yy,xx=-xx;
}
int main()
{
freopen("ray.in","r",stdin);
freopen("ray.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++) add(0,i),add(n+1,i);
for(int i=0;i<=n+1;i++) add(i,0),add(i,m+1);
for(int i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
}
sort(ALL(seg[0]));
sort(ALL(seg[1]));
scanf("%d%d",&x,&y);
scanf("%s",s);
xx=(s[0]=='N')?-1:1;
yy=(s[1]=='W')?-1:1;
reflect();
ans=0;
int st=x,ed=y,dx=xx,dy=yy;
do reflect();
while(!(x==st&&y==ed&&xx==dx&&yy==dy));
printf("%lld\n",flag?(ans>>1):ans);
return 0;
}