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≤106,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。
【数据范围】
子任务编号 | n≤ | 特殊性质 | 分值 |
---|---|---|---|
Subtask1 | 20 | 无 | 10 |
Subtask2 | 300 | 无 | 10 |
Subtask3 | 5000 | tp=1 | 10 |
Subtask4 | 5000 | 无 | 15 |
Subtask5 | 10^5 | tp=1 | 10 |
Subtask6 | 10^5 | 无 | 15 |
Subtask7 | 10^6 | tp=1 | 10 |
Subtask8 | 10^6 | 无 | 20 |
对于所有数据: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;
}
一定要记住开的空间要够!!!
不要害怕空间问题!!!
一般不会爆!!!