D

预处理勾股数然后暴力判断是否满足条件

#include <bits/stdc++.h>
using namespace std;
int i,j,k,n,m,x,y,t,p,q,T;
vector<pair<int,int> >b[10000010];
int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}
int main(){
    for (i=1;i<=3300;i++)
        for (j=i;j<=3300;j++)
            if (i*i+j*j<=10000000){
                b[i*i+j*j].push_back(make_pair(i,j));
            }
    scanf("%d",&T);
    while (T--){
        scanf("%d%d",&p,&q);
        x=gcd(p,q);p/=x;q/=x;
        int flag=0;
        for (i=0;i<b[p].size();i++){
            x=b[p][i].first;y=b[p][i].second;
            if (x*y==q){
                printf("%d %d\n",x,y);
                flag=1;break;
            }
        }
        if (flag==1)continue;
        printf("0 0\n");
    }
}

E

简单的二分DP

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k,a[N],b[N],f[N];
int main()
{
	//srand(time(0));
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	//int T; cin>>T; while(T--) work();
	cin>>n>>k; 
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for (int i=1;i<=n;i++){
        int l=1,r=i-1,ans=0;
        while (l<=r){
            int mid=l+r>>1;
            if (a[mid]<=a[i]-k)ans=mid,l=mid+1;else r=mid-1;
        }
        f[i]=f[ans]+1;
    }
    printf("%d\n",f[n]);
	return 0;
}

G

树形DP

一开始想复杂了

对于一个子树中是否有边要往上连其实是确定的。。。

#include <cstdio>
using namespace std;
const int N=100010;
const int mod=998244353;
int fi[200010],ne[200010],la[200010],a[200010];
int i,j,k,n,m,x,y,t;
int f[100010],fac[100010];
void add(int x,int y){
    k++;a[k]=y;
    if (fi[x]==0)fi[x]=k;else ne[la[x]]=k;
    la[x]=k;
}
int dfs(int x,int fa){
    int cnt=0;f[x]=1;
    for (int i=fi[x];i;i=ne[i])
        if (a[i]!=fa){
            cnt+=dfs(a[i],x);
            f[x]=1ll*f[x]*f[a[i]]%mod;
        }
    if (cnt&1){
        f[x]=1ll*cnt*fac[cnt-1]%mod*f[x]%mod;
    }
    else f[x]=1ll*f[x]*fac[cnt]%mod;
    return cnt+1&1;
}
int main(){
    scanf("%d",&n);
    for (i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    fac[0]=1;
    for (i=1;i<=n;i++)
        if (i&1)
            fac[i]=1ll*fac[i-1]*i%mod;
        else fac[i]=fac[i-1];
    dfs(1,-1);
    printf("%d\n",f[1]);
    return 0;
}

H

Kruscal合并边时建一个新点,边权为E-两棵子树权值和

然后倍增

#include <bits/stdc++.h>
using namespace std;
const int N=200010;
struct edge{
    int x,y,t;
}e[N];
int i,j,k,n,m,x,y,t,q,a[N],fa[N],size[N];
int f[N][19],g[N][19];
bool cmp(const edge&a,const edge &b){
    return a.t<b.t;
}
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void add(int x,int y,int t){
    f[x][0]=y;g[x][0]=t;
}
int main(){
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    scanf("%d%d%d",&n,&m,&q);
    for (i=1;i<=n;i++)scanf("%d",&a[i]);
    for (i=1;i<=n;i++)fa[i]=i,size[i]=a[i];
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&t);
        e[i]={x,y,t};
    }
    sort(e+1,e+1+m,cmp);int nn=n;
    for (i=1;i<=m;i++){
        x=e[i].x;y=e[i].y;
        if (find(x)==find(y))continue;
        int u=find(x),v=find(y);
        nn++;fa[nn]=nn;size[nn]=size[v]+size[u];
        add(u,nn,e[i].t-size[u]);add(v,nn,e[i].t-size[v]);
        fa[u]=nn;fa[v]=nn;
    }
    g[nn][0]=1100000000;
    for (k=1;k<=18;k++)
        for (i=1;i<=nn;i++)
            f[i][k]=f[f[i][k-1]][k-1];
    for (k=1;k<=18;k++)
        for (i=1;i<=nn;i++)
            g[i][k]=max(g[i][k-1],g[f[i][k-1]][k-1]);
    while (q--){
        scanf("%d%d",&x,&t);
        for (k=18;k>=0;k--)
            if (g[x][k]<=t){
                x=f[x][k];
            }
        printf("%d\n",size[x]+t);
    }
    return 0;
}

I

普普通通的背包DP。。。

#include <bits/stdc++.h>
using namespace std;
long long f[2][110][2610];
int v[110],t[110];
int i,j,k,n,m,x,y,K;
int main(){
    scanf("%d%d",&n,&K);
    for (i=1;i<=n;i++){
        scanf("%d%d",&v[i],&t[i]);
    }
    for (i=0;i<=K;i++)for (j=0;j<=2600;j++)f[0][i][j]=-1ll<<60;
    f[0][0][1300]=0;
    for (i=1;i<=n;i++){
        for (j=0;j<=K;j++)
            for (k=0;k<=2600;k++)f[i%2][j][k]=f[(i-1)%2][j][k];
        for (j=0;j<=K;j++)
            for (k=t[i];k<=2600;k++)
                f[i%2][j][k]=max(f[i%2][j][k],f[(i-1)%2][j][k-t[i]]+v[i]);
        for (j=1;j<=K;j++)
            for (k=2*t[i];k<=2600;k++)
                f[i%2][j][k]=max(f[i%2][j][k],f[(i-1)%2][j-1][k-2*t[i]]+v[i]);
        for (j=0;j<=K;j++)
            for (k=0;k<=2600-t[i];k++)
                f[i%2][j][k]=max(f[i%2][j][k],f[(i-1)%2][j][k+t[i]]+v[i]);
        for (j=1;j<=K;j++)
            for (k=0;k<=2600-2*t[i];k++)
                f[i%2][j][k]=max(f[i%2][j][k],f[(i-1)%2][j-1][k+2*t[i]]+v[i]);
    }
    long long ans=0;
    for (i=0;i<=K;i++)ans=max(ans,f[n%2][i][1300]);
    printf("%lld\n",ans);
    return 0;
}

J

BITSET求出每一位的K值然后AND起来

#include <unordered_map>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
int a[50010],s[50010],b[50010];
bitset<50001>B[50010],ans,yi;
int i,j,k,n,m,x,y,t,num,T;
unordered_map<int,int> mp;
char ch;
void print(bitset<50001> b){
    for (int i=1;i<=n;i++)printf("%d",(int)b[i]);printf("\n");
}
int main(){
    scanf("%d",&T);
    while (T--){
        mp.clear();mp[0]=0;
        scanf("%d\n",&n);
        for (i=1;i<=n;i++)yi[i]=1;ans=yi;
        for (i=1;i<=n;i++){
            scanf("%c",&ch);
            s[i]=s[i-1]+ch-'0';
        }
        for (i=1;i<=n;i++)s[i]=2*s[i]-i;
        scanf("\n");
        for (i=1;i<=n;i++){
            scanf("%c",&ch);
            b[i]=ch-'0';
        }
        for (i=1;i<=n;i++){
            B[i].reset();
            if (mp.find(s[i])==mp.end()){
                if (s[i]>s[i-1])B[i]=yi;
            }
            else{
                x=mp[s[i]];
                if (s[i]==s[i-1]+1){
                    B[i]=(B[x]<<(i-x))|(yi>>(n-(i-x)));
                }
                else B[i]=B[x]<<(i-x);
                B[i][i-x]=0;
            }
            // printf("=====\n");
            // print(ans);
            if (b[i]==0)ans&=yi^B[i];else ans&=B[i];
            // print(B[i]);
            // print(ans);
            // printf("=====\n");
            mp[s[i]]=i;
        }
        print(ans);
    }
}

K

对于4n就10011001...

4n+1就1001010011001...

4n+2就10010100101001...

4n+3就1001010010100101001...

小的情况特判即可

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,i;
    scanf("%d",&n);
    if (n==2)printf("10\n");
    else if (n==3)printf("Unlucky\n");
    else if (n==6)printf("011001\n");
    else if (n==7)printf("0110001\n");
    else if (n==10)printf("1000000100\n");
    else if (n==11)printf("00010000000\n");
    else if (n==15)printf("010101001000000\n");
    else{
        if (n==5)printf("01000\n");
        else{
            if (n%4==0)
                for (i=1;i<=n;i+=4)printf("1001");
            else if (n%4==1){
                printf("10010");
                for (i=6;i<=n;i+=4)printf("1001");
            }
            else if (n%4==2){
                printf("1001010010");
                for (i=11;i<=n;i+=4)printf("1001");
            }
            else{
                printf("100101001010010");
                for (i=16;i<=n;i+=4)printf("1001");
            }
            printf("\n");
        }
    }
}

M

神仙构造。。。不是很懂。。。

#include <cstdio>
using namespace std;
int n;
int main(){
    scanf("%d",&n);
    printf("%.9lf\n",1.0/(n*((n+1)/2)*((n+2)/2)));
}


告别纷扰,去寻找生活的宝藏。