开场被A劝退，写了得有50min于是不敢交了。unrated了喜闻乐见。
A：瞎猜都能猜到如果要走到那条直线上，进入直线的点横坐标或纵坐标与起点相同，离开直线的点横坐标或纵坐标与终点相同，证明脑补一下比较显然（事实上也就是以起点终点为对角点构成的矩形与该直线的交点）。看错题以为到直线上的那个点必须是整点，于是搞了半天exgcd。然而就算这样也不至于写这么长时间啊根本不知道自己在干啥。
#include#include #include #include #include #include using namespace std;#define ll long long#define double long doublechar getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int read(){ int 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<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}double ans,A,B,C,lx,ly,rx,ry;double dis_m(double x,double y,double p,double q){ return fabs(x-p)+fabs(y-q);}double dis_o(double x,double y,double p,double q){ return sqrt((p-x)*(p-x)+(y-q)*(y-q));}struct data{ double x,y;}a[2],b[2];int main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif A=read(),B=read(),C=read(); lx=read(),ly=read(),rx=read(),ry=read(); ans=fabs(rx-lx)+fabs(ry-ly); if (A&&B) { a[0].x=lx,a[0].y=(-C-A*lx)/B; a[1].y=ly,a[1].x=(-C-B*ly)/A; b[0].x=rx,b[0].y=(-C-A*rx)/B; b[1].y=ry,b[1].x=(-C-B*ry)/A; for (int i=0;i<2;i++) for (int j=0;j<2;j++) ans=min(ans,dis_m(lx,ly,a[i].x,a[i].y)+dis_o(a[i].x,a[i].y,b[j].x,b[j].y)+dis_m(b[j].x,b[j].y,rx,ry)); } printf("%.6Lf\n",ans); return 0;}
B：题意比较奇怪，做法相当显然，肯定要保证所有满足询问给出的条件的子集都只包含同一单一数字，类似背包的算一发方案数就行了，可以取个模。看起来询问补集也是一种询问方式，不过稍微想一下就知道是没有必要的。但这带来一种特殊情况，即只有两种数字时输出n。
#include#include #include #include #include #include using namespace std;#define ll long long#define N 110#define P 998244353 char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int 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<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,a[N],ans;int f[N][N*N],C[N][N];int main(){#ifndef ONLINE_JUDGE freopen("b.in","r",stdin); freopen("b.out","w",stdout);#endif n=read(); for (int i=1;i<=n;i++) a[i]=read(); f[0][0]=1; for (int i=1;i<=n;i++) for (int k=i;k>=1;k--) for (int j=10000;j>=a[i];j--) f[k][j]=(f[k][j]+f[k-1][j-a[i]])%P; C[0][0]=1; for (int i=1;i<=n;i++) { C[i][0]=C[i][i]=1; for (int j=1;j
C：考虑清楚最大匹配唯一究竟是什么。冷静分析能够发现其充要条件是该树只包含一个点或存在完美匹配。充分性比较显然，对于必要性，考虑如果不存在完美匹配，最大匹配中未匹配点的周围一定存在匹配点，可以将该匹配点改为与未匹配点匹配而匹配数不变，于是方案不唯一。那么就可以瞎dp了，我自己的做法是设f[i][0/1/2]分别表示 割开i与父亲的边，子树内的森林都满足条件/不割开i与父亲的边，i不与子树内点匹配/不割开i与父亲的边，i与子树内点匹配 的删边方案数，比较显然的有f[i][2]=Σ(f[k][1]·∏(f[son][0]+f[son][2])) (k为i某个儿子，son为除k以外i的儿子们) f[i][0]=f[i][2]+∏f[son][0] f[i][1]=∏(f[son][0]+f[son][2])。
#include#include #include #include #include #include using namespace std;#define ll long long#define N 300010#define P 998244353char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int 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<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,p[N],f[N][3],pre[N],suf[N],t;struct data{ int to,nxt;}edge[N<<1];void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}void dfs(int k,int from){ f[k][0]=f[k][1]=1;f[k][2]=0;int son=0;pre[0]=1; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=from) dfs(edge[i].to,k); for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=from) pre[++son]=(f[edge[i].to][0]+f[edge[i].to][2])%P; suf[son+1]=1;for (int i=1;i<=son;i++)suf[i]=pre[i]; for (int i=1;i<=son;i++) pre[i]=1ll*pre[i-1]*pre[i]%P; for (int i=son;i>=1;i--) suf[i]=1ll*suf[i+1]*suf[i]%P; int cnt=0; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=from) { cnt++; f[k][2]=(f[k][2]+1ll*f[edge[i].to][1]*pre[cnt-1]%P*suf[cnt+1])%P; f[k][0]=1ll*f[k][0]*f[edge[i].to][0]%P; } f[k][0]=(f[k][0]+f[k][2])%P; f[k][1]=pre[son];}int main(){#ifndef ONLINE_JUDGE freopen("c.in","r",stdin); freopen("c.out","w",stdout);#endif n=read(); for (int i=1;i
D：https://www.cnblogs.com/Gloid/p/9874122.html 可能和这个题比较相似。倍增算出每只鹦鹉的影响区间扩展2k次能到哪即可。只是口胡，不知道有没有锅。