emmm...作为本蒟蒻的实际意义上的第一篇博客，当然要认真写写才不反正也没什么人看
T1 题意简述：求二元不定方程的正整数解组数。
T≤10000，-1,000,000≤a,b,c≤1,000,000
解题思路：扩展欧几里得即可，关于负数可以特判。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #define ll long long using namespace std; ll T; ll gcd(ll x,ll y) { while(x%y!=0) {ll tmp=y;y=x%y;x=tmp;} return y; } ll spj(ll &x,ll &y,ll &z) { if(!x&&!y&&!z) {printf("ZenMeZheMeDuo ");return 1;} if(!x&&!y&&z) {printf("0 ");return 1;} if(!y) swap(x,y); if(!x&&y&&!z) {printf("0 ");return 1;} if(!x&&y&&z) { if((y<0&&z>0)||(y>0&&z<0)) {printf("0 ");return 1;} if(z%y!=0) {printf("0 ");return 1;} if(x%y==0) {printf("ZenMeZheMeDuo ");return 1;} } if(x<0&&y<0&&z>=0) {printf("0 ");return 1;} if(x<0&&y<0&&z<0) x=-x,y=-y,z=-z; return 0; } void exgcd(ll a,ll b,ll &x,ll &y) { if(!b) { x=1;y=0; return; } exgcd(b,a%b,y,x); y=y-a/b*x; } int main() { freopen("fuction.in","r",stdin); freopen("fuction.out","w",stdout); scanf("%lld",&T); while(T--) { ll u,v,w; scanf("%lld%lld%lld",&u,&v,&w); if(spj(u,v,w)) continue; ll tmp=gcd(u,v); if(w%tmp!=0) {printf("0 ");continue;} if((u<0&&v>0)||(u>0&&v<0)) {printf("ZenMeZheMeDuo ");continue;} u=u/tmp;v=v/tmp;w=w/tmp; ll x,y; exgcd(u,v,x,y); x*=w,y*=w; if(x>0&&y<=0) swap(x,y),swap(u,v); if(x<=0) { ll xx=x; x+=((0-xx)/v+1)*v; y-=((0-xx)/v+1)*u; } if(x<=0||y<=0) {printf("0 ");continue;} ll ans=0; ans=y/u+(y%u>0); if(ans>65535) {printf("ZenMeZheMeDuo ");continue;} printf("%lld ",ans); } return 0; }
T2 题意简述：有一棵点数为n的树，树边有边权。将m个点染成黑色，并将其他的点染成白色。会获得
黑点两两之间的距离和加上白点两两之间的距离和的收益。问收益最大值是多少。
0≤m≤n≤2000，1≤c≤1,000,000
解题思路：考虑（u，v）这条边的贡献，发现在这条边两边的子树上的黑点都可以两两配对，白点
亦然。因此贡献为
（ Black（u）* Black（v）+ White（u）* White（v））* val（u，v）
发现可以用树形DP递推至根节点，在计算贡献时用一个背包即可。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #define ll long long using namespace std; ll n,blk,cnt,head[2001],siz[2001],dp[2001][2001]; struct uio{ ll nxt,to,val; }edge[4001]; void add(ll x,ll y,ll z) { edge[++cnt].nxt=head[x]; edge[cnt].to=y; edge[cnt].val=z; head[x]=cnt; } void dfs(ll x,ll fa) { siz[x]=1; dp[x][0]=dp[x][1]=0; for(ll i=head[x];i;i=edge[i].nxt) { ll y=edge[i].to; if(y==fa) continue; dfs(y,x); siz[x]+=siz[y]; } for(ll i=head[x];i;i=edge[i].nxt) { ll y=edge[i].to,z=edge[i].val; if(y==fa) continue; for(ll j=min(siz[x],blk);j>=0;j--) for(ll k=0;k<=min(j,siz[y]);k++) if(dp[x][j-k]!=-1) { ll wei=z*(k/*此子树黑点个数*/*(blk-k)/*另一子树黑点个数*/+ (siz[y]-k)/*此子树白点个数*/*(n-blk-(siz[y]-k))/*另一子树白点个数*/); dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[y][k]+wei); } } } int main() { freopen("coloration.in","r",stdin); freopen("coloration.out","w",stdout); scanf("%lld%lld",&n,&blk); for(ll i=1;i<n;i++) { ll u,v,w; scanf("%lld%lld%lld",&u,&v,&w); add(u,v,w),add(v,u,w); } memset(dp,-1,sizeof(dp)); dfs(1,0); printf("%lld ",dp[1][blk]); return 0; }
T3 题意简述：
n，m，k≤100000
解题思路：首先感谢坐在我旁边的ErkkiErkko大佬教会我这道题。ErkkiErkko大佬TQL！！！
容易看出，光线改变方向的次数是O（n+m+k）级别的，因此我们可以进行模拟。
把障碍存在set里（边界也要存），每次由光线所在位置及朝向方向+lower_bound即可得
出下一障碍位置。
时间复杂度O（（n+m+k）logn ）。
由于光线不会相交在块内 <=== ErkkiErkko大佬证明得出
因此不必去重，且结束条件仅两种：
1.光线回到起点，且路径上的每个点都只经过一次
2.光线回到起点，且路径上的每个点都经过了两次
对于这两种情况，只需记录是否曾沿反方向经过了起点，若是则将ans/2，否则直接输出
ans即可。
代码：尚未码出，稍后补足。（咕咕咕？）