目录

E Strange Integers:

D Strange Fractions:

G Edge Groups

I Steadily Growing Steam:

H Life is a Game:

K Circle of Life:

签到题

题意为给定一个数组和一个数k

问能找出几对绝对值相差超过k的数

考虑直接排序二分，然后每次更新数即可

const int N=1e6+10;
int a[N];
signed main(){
    int n,k;
    cin>>n>>k;
    fer(i,1,n) scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    int ans=0;
    int t=a[1];
    int it=1;
    while(it!=n+1)
    {
        t=a[it];
        t+=k;
        ans++;
        it=lower_bound(a+1,a+1+n,t)-a;
    }
    cout<

D Strange Fractions:

题意为给定p ，q 求得一对a，b使得p/q=a/b+b/a

一道解方程题，只需要设x=a/b,则b/a=1/x,然后设k=p/q,

原式等于 ,只需要导出已知k求x的解即可

直接求根公式

当判别式<0，或判别式开跟不是整数时就是无解，即当

大于等于0时，且为整数时

有

为了保证整数，我们取a等于,b=2*q即可

代码如下

signed main()
{
    int t = 1;
    scanf("%lld",&t);
    while(t--)
    {
        bool bol=true;
        int p,q;
        scanf("%lld%lld",&p,&q);
        int k=p*p-4*q*q;
        int kk=sqrt(k);
        if(kk*kk==k)
            bol=true;
        else
            bol=false;
        int gcdd=__gcd(p-kk,q*2);
        if(!bol)
            printf("0 0n");
        else
        {
            printf("%lld %lldn",(p-kk)/gcdd,q*2/gcdd);
        }
    }
    return 0;
}

G Edge Groups

给定一棵树，让我们把边分成(n-1)/2组，使得每组中有且仅有两条边，而且两条边公用同一个顶点，求分成的组个数，答案对998244353取模

首先我们可以一步一步想，如果我们知道有x条边，让我们把他分成两两一组，有几种方法？

这个答案应该是不难的，答案应该是

我们把组合数乘开，上面是

下面是

我们把上下分母约去，上面分子约去奇数项，可以得到答案即为

接下来我们只需要思考如何找到每个节点可以用几条边，这样就可以树形dp

首先我们假设对于节点f，他有两种不同的儿子u和v

儿子u有两个儿子，儿子v有三个儿子
 

那么对于f-u这条边1，他对f是可用的，因为儿子u可以内部消化完全不需要这条边

反之对于儿子v，由于他的子树有奇数条边，所以必须要加上f-v这条边才能分配

所以对于f，f-v这条边就是不可用的

问题即迎刃而解

代码如下：

const int N=1e6+10;
const int mod=998244353;
vector v[N];
int f[N];
bool dfs(int son,int fa){
    f[son]=1;
    int usedg=0;
    for(auto t:v[son]){
        if(t==fa) continue;
        if(!dfs(t,son)){
            usedg++;
        }
        f[son]=f[son]*f[t]%mod;
 
    }
    for(int i=1;i<=usedg;i+=2){
        f[son]=(f[son]*i)%mod;
    }
    return usedg&1;
}
signed main()
{
    int n;
    cin>>n;
    int a,b;
    fer(i,1,n-1){
        scanf("%lld%lld",&a,&b);
        v[a].pb(b);
        v[b].pb(a);
    }
    dfs(1,0);
    cout< 
I Steadily Growing Steam: 
有n张牌,每张牌有一个价值w和点数t，先选择至多m张牌将其点数 t 翻倍,再从n张牌中选若干张牌分成两堆,要求两堆内点数之和相等,求选出的牌的价值w之和的最大值.
 
很明显是一道类似于背包的dp题，只不过这道题要开三维
 
和背包一样，我们设 f[i][j][k] 是从前i个物品中选的最大价值，其中j代表有我们把其中的j个点数翻倍了，很明显j大于等于0，小于等于m
 
第三维是两堆价值的插值，由题意得在-2600和2600之间，我们直接把他加2600，变成0-5200
 
然后是转移方程
 
不选第i个时： f[i] [j] [k] = f[i-1] [j] [k]
 
选第i个放入一背包 f[i] [j] [k] = max(f[i] [j] [k],f[i-1] [j] [k-t[i]]+v[i])
 
选第i个放入第二个背包 f[i] [j] [k] = max(f[i][j][k],f[i-1][j][k+t[i]]+v[i])
 
选第i个放入第一个背包并翻倍 f[i] [j] [k] = max(f[i] [j] [k],f[i-1] [j-1] [k-2*t[i]]+v[i])
 
选第i个放入第二个背包并翻倍 f[i] [j] [k] = max(f[i] [j] [k],f[i-1] [j-1] [k+2*t[i]]+v[i])
 
直接开三维空间会炸，由于我们求i是只用到i-1的状态，所以直接开2，上下循环即可
 
关键代码如下
 
const int N=105,M=6005;
const int inf=-1e18
int t[N],v[N];
int f[2][N][M];
signed main()
{
	int n,m;
	cin>>n>>m;
	fer(i,1,n) {
        cin>>v[i]>>t[i];
    }
	fer(i,0,m){			
		fer(j,0,5200){
            if(j==2600) continue;
			f[0][i][j]=inf;
        }
    }
	fer(i,1,n)
		fer(j,0,m)
			fer(k,0,5200)
			{
                int x;
                if(i&1) x=1;
                else x=0;
				f[x][j][k]=f[x^1][j][k];
				if(k-t[i]>=0){
                    f[x][j][k]=max(f[x][j][k],f[x^1][j][k-t[i]]+v[i]);
                }
				if(k+t[i]<=5200){
                    f[x][j][k]=max(f[x][j][k],f[x^1][j][k+t[i]]+v[i]);
                }
				if(j)
				{
					if(k-2*t[i]>=0)
						f[x][j][k]=max(f[x][j][k],f[x^1][j-1][k-2*t[i]]+v[i]);
					if(k+2*t[i]<=5200)
						f[x][j][k]=max(f[x][j][k],f[x^1][j-1][k+2*t[i]]+v[i]);
				}
			}
	cout< 
H Life is a Game: 
 题意为给定一张无向图，每个点有点权每条边有边权
 
规则是每次给我们一个初始能量值，每到一个新的点，我们的能量就可以加上这个点的点权，但我们要想走过一条边，需要能量大于该边的权值，问我们每次最大能获得多少能量
 
首先暴力的想，由于获取能量的路径只有到达点，那我们肯定要尽可能多的到达点，但边会限制我们到达新的点
 
第一步我们肯定要把整张图变成一颗最小生成树，因为经过边权大的边对我们毫无意义，我们只需要花最小代价去最多的点即可
 
其次我们肯定会想到写bfs来判断某个点能不能达到，但1e5个询问，每次最坏为n，总复杂度为n*n肯定过不了
 
这时候我们可以引入一个数据结构————kruskal重构树
 
详解可以百度一下或者去看->
 
(31条消息) Kruskal重构树详解_lxrrrrrrrr的博客-CSDN博客
 
在这棵树上除了代表原图点的叶子节点，上面点的点权必定大于他子树所有点的点权
 
也就是说，只要能量大于虚点A的点权，那么A的子树的能量我们都可以获取到，这个可以倍增时预处理一下
 
由于其独特的性质，在处理这道题中，我们可以每次通过起始点尽可能往上跳，每次跳完我们的能量就可以变成跳之后点的子树权值，直至跳不上去或跳到根节点，
 
这样我们可以把复杂度压到nlogn
 
代码如下：
 
#include 
#include 
#define fer(i,a,b) for(int i=a;i<=b;i++)
#define der(i,a,b) for(int i=a;i>=b;i--)
#define int long long
#define pb push_back
#define pll pair
#define ld long double
using namespace std;
const int N =200010,M=100010;
int n,m,k;
struct edge
{
    int a,b,w;
    bool operator<(const edge& ee)const { return w < ee.w; }
}ed[M];
vector e[N];
int a[N], p[N], stw[N];
int d[N];
int fa[N][18];
int find(int x) {
    return p[x]==x?p[x]:p[x]=find(p[x]);
}
int exkruskal() {
    sort(ed+1,ed+1+m);
    fer(i,1,2*n) p[i]=i;
    int cnt=n;
    fer(i,1,m) {
        int a=find(ed[i].a),b=find(ed[i].b);
        if (a^b){
            d[++cnt]=ed[i].w;
            p[a]=p[b]=cnt;
            e[cnt].push_back(a);
            e[cnt].push_back(b);
        }
    }
    return cnt;
}
int exlca(int x) { 
    int sum=a[x];
    for (auto j :e[x]){
        fa[j][0]=x;
        for (int i=1;i<=17;i++)
            fa[j][i]=fa[fa[j][i-1]][i-1];
        sum+=exlca(j);
    }
    stw[x]=sum;
    return sum;
}
signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    fer(i,1,n) cin>>a[i];
    fer(i,1,m) {
        int a,b,x;
        cin>>a>>b>>x;
        ed[i] = {a,b,x};
    }
    n=exkruskal();
    exlca(n);
    d[0] = 1e18;
    fer(i,1,k) {
        int x,q;
        cin>>x>>q;
        int ans=a[x]+q;
        while (x!= n)
        {
            int x1=x;
            for (int i=17;i>=0;i--)
                if (d[fa[x][i]]<=ans) x=fa[x][i];
            if (x==x1) break;
            ans=stw[x]+q;
        }
        cout<
 
K Circle of Life: 
构造题，大致意思是给一个01串，每一次变换之后第i个1会分裂成两个1到i-1和i+1，如果两个分裂的撞在一起了则会消失，要求我们输出一个n位的01串，使其在2*n次变换之内可以变回原样，即出现循环
 
首先这种构造题一般都是有结论性的特殊序列
 
比如11，00，101，010这种，根据题意首先不可能全是1或0
 
010一次会变成101，第二次会直接000，也肯定不行
 
而我们发现，像1001，0110这两个串，他们是在此变换中互逆的，可以考虑用他们构造循环
 
1001-> 0110 -> 1001
 
100110-> 011001 -> 100110
 
我们发现对于n是偶数，我们只需要不断交错添加01和10，即可构造成功
 
而对于奇数 0101001 -> 1000110 -> 0101001 也能循环
 
我们发现前面加个010，再结合后面偶数的答案拼接在一起，即可构造
 
所以我们对于n是奇数，先输出010，然后n-=3，在和偶数一起算即可
 
偶数直接无脑10加01加10
 
代码如下：
 
signed main(){
    int n;
	cin>>n;
	if(n==1||n==3){
        cout<<"Unlucky";
    }
	else{
		if(n%2)	
        {
            cout<<"010";
            n-=3;
        }
		n/=2;
		fer(i,0,n-1)
			if(i&1){
                cout<<"01";
            }
			else cout<<"10";
	}

}