2024.7.22

2024.7.22 【“大暑三秋近，林钟九夏移。桂轮开子夜，萤火照空时。”】

Monday 六月十七 大暑

T1 难（nan）

【题目描述】

给定两个字符串a,b，从a中选一段前缀，b中选一段后缀（前后缀都可以为 空），并将选出的后缀拼在选出的前缀后面。 你需要求出有多少种本质不同的串（可以为空）。

【输入格式】

从文件nan.in 中读入数据。 共2行，每行1个字符串，依次表示a,b。保证a,b仅由小写字母组成。

【输出格式】

输出到文件nan.out 中。 共1行，1个数，表示答案。

【样例输入1】

abc cba 

【样例输出1】

13 

【样例23】

见选手目录下的ex nan2∼3.in 和ex nan2∼3.out。

【数据范围】

对于100% 的数据，1≤|a|,|b|≤106。

subtask 1(40 分)：|a|,|b| ≤ 100。

Subtask 2(60 分)：无特殊限制。

考虑打表找规律

小数据不难发现，

将两个字符串重复字符部分个数相乘

用能产生的字符总个数减去即可

//2024.7.22
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn long long
#define int long long
constexpr int oo = 1000006;

char st[oo],sp[oo];

long long out;

itn ton[2][26];

signed main(){
	//freopen("nan.in","r",stdin);
	//freopen("nan.out","w",stdout);
	
	cin >> st;
	cin >> sp; 
	
	itn n = strlen(st);
	int m = strlen(sp);
	
	out = (n+1)*(m+1);
	
	for (itn i=0;i<n;i++)
		ton[1][st[i]-'a']++;	
	for (itn i=0;i<m;i++)
		ton[0][sp[i]-'a']++;
	
	for (itn i=0;i<26;i++)
		out -= ton[1][i]*ton[0][i];
	
	cout << out;
	return 0;
}

T2 砝码（weight）

【题目描述】

有n个砝码，每个砝码都有初始重量ai。Q次操作，每次操作有下列两种： •1,l,r,x：表示把l到r的所有ai变成x •2,l,r,x：查询l到r的所有砝码，每个砝码可以用无数次，是否能称出重量x ai和所有的x都不大于m。 保证ai和所有操作1的x总共最多不超过10种数字。 注意砝码只能放在同一侧。

【输入格式】

从文件weight.in中读入数据。 第一行三个整数n,m,Q。 接下来一行n个整数ai。 接下来Q行每行四个整数opt,l,r,x表示一次操作。opt=1表示操作1，opt=2 表示操作2。

【输出格式】

输出到文件weight.out中。 对于每个2操作。输出一行‘Yes’或者‘No’表示能否称出重量x。

【样例输入1】

3 3 1 2 3 2 1 3 2 1 1 3 3 2 1 3 2 

【样例输出1】

Yes No

【数据范围】

对于30%的数据，n,m,Q≤10 对于50%的数据，n,m,Q≤1000 对于另外20%的数据，opt=2 对于100% 的数据，n,Q≤10^6,m≤105

使用线段树维护修改，

考虑到最多只有十种不同的重量

使用状态压缩记录区间内重量种类

使用背包考虑能满足的重量即可

//2024.7.22
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define itn int
constexpr int oo = 1000006; 
itn num[oo];
itn n,m,q;

struct nd{itn opt,l,r,x;}que[oo];

itn mp[oo];
itn mt[300005];
int top;
itn tree[oo<<2];
itn tag[oo<<2];

void pushup(itn x){tree[x]=tree[x<<1]|tree[x<<1|1];}
void build(itn l,itn r,int x){
	if(l==r){
		tree[x]=(1<<(mp[num[l]]-1));
		return;
	}
	int mid = (l+r)>>1;
	build(l,mid,x<<1);build(mid+1,r,x<<1|1);
	pushup(x);
}
void addtag(itn x,itn p){
	tree[x] = (1<<(mp[p]-1));
	tag[x] = p;
}
void pushdown(int l,itn r,itn x){
	if (tag[x]){
		int mid = (l+r)>>1;
		addtag(x<<1,tag[x]);
		addtag(x<<1|1,tag[x]);
		tag[x] = 0;
	}
}
void updata(itn l,itn r,itn nl,itn nr,itn x,itn p){
	if (l>=nl&&r<=nr){addtag(x,p);return;}
	int mid = (l+r)>>1;
	pushdown(l,r,x);
	if (mid>=nl) updata(l,mid,nl,nr,x<<1,p);
	if (mid<nr) updata(mid+1,r,nl,nr,x<<1|1,p);
	pushup(x);
}
int query(itn l,itn r,itn nl,itn nr,int x){
	if (l>=nl&&r<=nr){
		return tree[x];
	}
	int mid = (l+r)>>1,out = 0;
	pushdown(l,r,x);
	if (mid>=nl)out|=query(l,mid,nl,nr,x<<1);
	if (mid<nr) out|=query(mid+1,r,nl,nr,x<<1|1);
	pushup(x);
	return out;
}

bool b[1025][100005];

signed main(){
    freopen("weight.in","r",stdin);
    freopen("weight.out","w",stdout);

    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

	cin >> n >> m >> q;
	for (itn i=1;i<=n;i++){
		cin >> num[i];
        if(!mp[num[i]])
            mp[num[i]] = ++top,mt[top] = num[i];
    }
    for (int i=1;i<=q;i++){
        cin >> que[i].opt >> que[i].l >> que[i].r >> que[i].x;
        if (!mp[que[i].x])
            mp[que[i].x] = ++top,mt[top] = que[i].x;
    }
    for (int i=0;i<1024;i++) b[i][0] = 1;
	for (int i=1;i<1024;i++)
		for (int j=1;j<=10;j++)
			if (i&(1<<(j-1)))
				for (int k=mt[j];k<=m;k++)
					b[i][k] |= b[i][k-mt[j]];
	build(1,n,1);
    for (int k=1;k<=q;k++){
        int opt = que[k].opt;
        itn l = que[k].l;
        itn r = que[k].r;
        int x = que[k].x;
        if (opt==1){
            updata(1,n,l,r,1,x);
        }
        else {
            itn p = query(1,n,l,r,1);
//            cout<<p<<'\n';
            if (b[p][x]) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

T3 交易（trade）

【题目描述】

小L是一个商人，特长是靠交易物品从中获利。通过某种神必手段，小L得 知了未来n天某种物品在市场上的价格，小L每天可以执行以下三种操作（假设 当天这种物品的市场价为x金币）：

1.用x金币买入一个物品（注意不能买多个）。

2.以x金币的价格卖出一个物品（注意不能卖多个且之前必须有至少一个物品）。

3.什么也不做。

假设小L一开始有无限多个金币且没有该种物品，且他一定会使用让自己赚 钱最多的策略交易物品。现在小Q想知道小L最多能赚多少个金币。由于小L不 想告诉小Q每天的价格，只告诉他每天的价格只有可能是1金币或者2金币。现 在他想知道有多少种可能的情况，使得小L最多能赚到k个金币。

【输入格式】

从文件trade.in中读入数据。 输入共两行，第一行为一个正整数tp，表示询问类型。 若tp=1，则第二行有两个正整数n,k，表示天数和小L赚的金币个数。 若tp=2，则第二行有一个正整数n，表示天数。

【输出格式】

输出到文件trade.out中。 若tp=1，则输出一行一个整数ans，表示小L最多能赚取k个金币的方案 数。答案对998244353取模。 若tp=2，则输出一行一个整数ans，设wayk表示最多赚取k个金币的方案 数，则： ans=( ⌊n 2⌋ ∑ i=0 233i×wayi)mod998244353

【样例输入1】

 1 4 2

【样例输出1】

 2

【样例解释1】

有两种方案，每天的价格分别是：[1,1,2,2]，[1,2,1,2]。

【样例2】

见选手目录下的extrade2.in和extrade2.out。

【数据范围】

对于所有数据：1≤n≤10^6,0≤k≤⌊n/ 2 ⌋。

原题，

考虑将，每个1，2天数看作左括号，右括号

考虑一定数量下的括号匹配

记录每个左右括号数量

因为左右括号不确定，

所以答案要乘上(n-2*k+1)

//2024.7.22
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn long long 
#define int long long 
constexpr int oo = 1000006;
constexpr int mod = 998244353;

itn opt;
itn n,k;

itn c[oo],ic[oo];
int inv[oo];

signed main(){
    freopen("trade.in","r",stdin);
    freopen("trade.out","w",stdout);

    cin >> opt >> n;
    inv[1] = c[1] = ic[1] = 1;
    c[0] = ic[0] = 1;
    for (itn i=2;i<=n;i++){
        c[i] = c[i-1]*i%mod;
        inv[i] = inv[mod%i]*(mod-mod/i)%mod;
        ic[i] = inv[i]*ic[i-1]%mod;
    }
    if (opt==1){
        cin >> k;
        itn p = c[n]*ic[k]%mod*ic[n-k]%mod;
        itn q = c[n]*ic[k-1]%mod*ic[n-k+1]%mod;
        cout << (n-2*k+1)*(p-q+mod)%mod;
    }
    else {
        int out = 0;
        itn ned = 1;
        for (itn i=0;i<=n/2;i++){
            itn p = c[n]*ic[i]%mod*ic[n-i]%mod;
            itn q = c[n]*ic[i-1]%mod*ic[n-i+1]%mod;
            (out += ned*(n-2*i+1)%mod*(p-q+mod)%mod)%=mod;
            ned = ned * 233%mod;
        }
        cout << out;
    }
    return 0;
}

一定要记住开的空间要够！！！

不要害怕空间问题！！！

一般不会爆！！！