MC党狂喜系列比赛
T1 命令方块
题目描述
实际上这道题与命令方块没有什么关系。
给定 \(n\) 个字符串 \(s_i\), 将它们按给出的顺序排开。你每次可以交换任意两个字符串的位置。通过交换, 这些字符串最终需要满足如下的性质:
对于任意的 \(i<j<k\) , 必须有: \(lcp(s_i,s_j) \ge lcp(s_i,s_k)\) 以及 \(lcp(s_j,s_k) \ge lcp(s_i,s_k)\)
其中 \(lcp(s,t)\) 的定义为: 字符串 \(s\) 和 \(t\) 的最长公共前缀的长度。如 \(lcp(abc, abd)=2\), 而 \(lcp(abc,abcd)=3\) 。
请按顺序输出你交换了哪些字符串。保证存在一种方案, 使得交换之后所有字符串满足上述性质。并 且可以证明, 在题目给定的范围下, 这样的方案一定存在, 并且你所需要的最少交换次数不会超过 \(10^6\) 次。
输入格式
输人文件名为 block.in。
第一行为一个正整数 \(n\), 代表字符串的个数。
接下来 \(n\) 行, 每行一个字符串, 代表最初的 \(s_i\) 。
输出格式
输出文件名为 block.out。
第一行为一个正整数 \(m\), 代表你的交换次数。
接下来 \(m\) 行, 每行两个正整数 \(a,b\), 代表你交换的两个字符串的位置。
Special Judge 将会按顺序完成你给出的交换操作, 并判定最后得到的字符串序列是否合法。如果你 输出的 \(m\) 大于 \(10^6\), 或者输出格式不正确, 将被认为是答案错误。如果你的答案合法并且是正确的, 你 将会得到对应测试点的得分, 反之不得分。
样例
输入数据 1
3
abcd
a
abd
输出数据 1
1
1 2
对于第一个样例： 交换后的字符串序列为：a, abcd, abd，不难发现，这是符合要求的。
数据规模与约定
对于全部的数据,\(n≤106,\Sigma∣s_i∣\le 10^7\), 字符串中的所有字符均属于小写英文字母。
| 测试点编号 | \(n\) 的范围 | 每个字符串的长度\(∣s_i∣\) | 字符串的总长度 \(∑∣s_i∣\) |
|---|---|---|---|
| 1,2 | \(n≤10\) | \(∣s_i∣≤10\) | \(∑∣s_i∣≤100\) |
| 3,4 | \(n≤10^3\) | \(∣s_i∣≤10^3\) | \(∑∣s_i∣≤10^6\) |
| 5,6,75,6,7 | \(n≤10^5\) | \(∣s_i∣≤10^5\) | \(∑∣s_i∣≤10^5\) |
| 8,9,108,9,10 | \(n≤10^6\) | \(∣s_i∣≤10^7\) | \(∑∣s_i∣≤10^7\) |
题解
我们用这些字符串构建出一棵字典树, 我们发现, 按照字典树的任意一种 dfs 序输出字符串都可以 获得一个合法的答案。
简单起见, 我们直接按字典序输出字符串即可。因此, 将所有字符串使用 sort 排序即可。 如何输出排序过程呢?
假设排序前的字符串分别为 \(s_1,s_2⋯s_n\), 排序后变成了: \(s_{p_1},s_{p_2}⋯s_{p_n}\) 。
排序的过程就是一个将 \(1,2⋯n\) 排序成 \(p_1,p_2 \cdots p_n\) 的过程。
我们可以每次找到任意一个不在应该在的位置上的数字 x, 将 x 与它本应该在的位置上的数字交换。
这样, 在 n 步之内, 所有数字都可以归位。
复杂度为 \(\mathcal O(nlogn)\)
丑陋的代码
#include<bits/stdc++.h>
using namespace std;
struct node{
string s;
int id;
}p[1000010];
int n,ans,num[1000010][2];
bool vis[1000010];
bool cmp(node a,node b){
return a.s<b.s;
}
void dfs(int x){
if(p[x].id==x) return ;
num[++ans][1] = x;num[ans][0] = p[x].id;
swap(p[x],p[p[x].id]);
vis[x] = true;
dfs(p[x].id);
}
int main(){
freopen("block.in","r",stdin);
freopen("block.out","w",stdout);
scanf("%d",&n);
for(int i = 1;i<=n;i++){
p[i].id = i;
cin>>p[i].s;
}
for(int i = 1;i<=n;i++){
if(p[i].id==i) vis[i] = true;
if(!vis[i])dfs(i);
}
printf("%d\n",ans);
for(int i = ans;i>=1;i--)
printf("%d %d\n",num[i][0],num[i][1]);
return 0;
}
个人觉得更简洁的标程
#include <bits/stdc++.h>
using namespace std;
const int MX = 1000005;
int n;
string str[MX];
int rak[MX], pos[MX], seq[MX];
vector<pair<int, int> > opr;
int main()
{
freopen("block.in", "r", stdin);
freopen("block.out", "w", stdout);
cin.sync_with_stdio(0);
cin >> n;
for(int i=1; i<=n; i++) cin >> str[i], pos[i] = i;
sort(pos+1, pos+n+1, [=](int a, int b){return str[a]<str[b];});
for(int i=1; i<=n; i++) rak[pos[i]] = i;
for(int i=1; i<=n; i++)
{
if(pos[i] != i)
{
opr.push_back(make_pair(pos[i], i));
swap(rak[i], rak[pos[i]]);
swap(pos[i], pos[rak[pos[i]]]);
}
}
printf("%d\n", opr.size());
for(auto i : opr) printf("%d %d\n", i.first, i.second);
return 0;
}
T2 骨粉
题目描述
在我的世界中, tick 是最基本的计时单位。
在我的世界中, 骨粉富含各类无机盐, 可以促进作物的生长。
现在你种植了 \(n\) 棵小麦, 它们分别还有 \(t_i\) 个 tick 才能成熟。当\(t_i≤0\) 时, 我们认为这棵小麦已经 成熟了。
每一个 tick 内, 你可以给某一棵小麦施加一个单位的骨粉 (你有无限的骨粉), 使这个小麦的瞬间生 长 \(x\) tick。同时, 每一棵小麦（包括施加骨粉的那一棵）还会自然生长 1 tick。
如果你按照最优的方式分配骨粉, 在 \(s\) tick 后, \(t_i\) 最大的小麦的 \(t_i\) 最小是多少? 如果所有小麦都已 经成熟, 请输出 \(0\) 。
输入文件
输入文件为 bone.in。
第一行三个整数 \(n,m,x\), 代表小麦的棵数, 询问的个数, 骨粉的效用。
第二行 \(n\) 个整数 \(t_i\), 代表每棵小麦还有多少个 tick 才能成熟。
接下来 \(m\) 行, 每行一个整数 \(s_i\), 代表一次询问。
输出文件
共 \(m\) 行, 每行一个整数, 代表每次询问的答案。
样例
输入数据 1
5 4 1
1 2 3 4 5
1
2
3
1000
输出数据 1
3
2
0
0
对于第一个样例：
一种最优的分配骨粉的方式是：
第一个 tick：分配给第 5 棵小麦。
第二个 tick：分配给第 4 棵小麦。
第三个 tick：分配给第 5 棵小麦。
按照如上的分配方式，不难得到样例的答案。
数据规模
对于全部的数据, $1≤n,m≤105,0≤s_i≤10,1≤x,t_i≤10{18},1≤∑t_i≤10 $
题解
首先我们不用管小麦自然生长造成的影响，只看施加骨粉的影响
因为自然生长是对所有小麦都加上一个时间 \(t\) ，可以放到最后一起处理
对于施加骨粉而言，最优的一定是在当前时刻 \(t_i\) 最大的小麦施加骨粉
很容易用这个思路写出一个暴力程序
再思考优化，想到了二分答案，\(\mathcal O(n)\) 判断所有的小麦施加次数是否超时
每棵小麦需要 $\max(⌈(t_i−v)/x⌉,0) $ 数量的骨粉。
为了能够更快的得到小麦所需要的骨粉数量，让我们来推一下式子
破口大骂中
根据这个式子便可以看出我们只需要算出有多少小麦满足 \(t_i >v \&\& (t_i \bmod x)>(v \bmod x)\) 我们可以用主席树实现或是离线+线段树
时间复杂度$\mathcal O(n\ log \ n+m \ log^2 \ n) $
好了上代码
#include<bits/stdc++.h>
#define int long long
#define N 100010
#define mid ((l+r)>>1)
using namespace std;
struct node{
int l,r,dat;
}t[N<<6];
int n,m,k,cnt,val[N],tim[N],sum[N],rot[N];
void add(int &p,int l,int r,int q,int x){
t[++cnt] = t[p];p = cnt;
if(l==r) t[p].dat+=x;
else{
if(q<=mid) add(t[p].l,l,mid,q,x);
else add(t[p].r,mid+1,r,q,x);
t[p].dat = t[t[p].l].dat+t[t[p].r].dat;
}
}
int query(int p,int l,int r,int ql,int qr){
if(!p) return 0;
else if(ql<=l&&qr>=r) return t[p].dat;
else if(ql>r||qr<l) return 0;
else return query(t[p].l,l,mid,ql,qr)+query(t[p].r,mid+1,r,ql,qr);
}
int check(int x){
int res = 0;
int p = lower_bound(tim+1,tim+n+1,x)-tim;
res = sum[p]-(x/k)*(n-p+1);
res+=query(rot[p],0,k,x%k+1,k);
return res;
}
int work(int t){
int l = 0,r = tim[n],ans = 0;
while(l<=r){
if(check(mid)<=t){
ans = mid;
r = mid-1;
}else l = ans = mid+1;
}
return max(ans-t,0ll);
}
signed main(){
freopen("bone.in","r",stdin);
freopen("bone.out","w",stdout);
scanf("%lld%lld%lld",&n,&m,&k);
for(int i = 1;i<=n;i++)
scanf("%lld",&tim[i]);
sort(tim+1,tim+n+1);
for(int i = 1;i<=n;i++)
val[i] = tim[i]/k;
for(int i = n;i>=1;i--){
sum[i] = sum[i+1]+val[i];
rot[i] = rot[i+1];
add(rot[i],0,k,tim[i]%k,1);
}
for(int i = 1;i<=m;i++){
int t;
scanf("%lld",&t);
printf("%lld\n",work(t));
}
return 0;
}
T3 字符串问题
这题貌似在CF上有原题，可惜没找到
题目描述
经过一番斗争以后，高钧终于放弃了抵抗
现在高匀有一个长度为 n 的由数字字符 0 ∼ 9 组成的字符串，在感受 alb 的快乐 之前，他有一个最后的问题
高匀有 k 个加号，他想将这 k 个加号插入到这个字符串中组成一个合法的表达式
合法的表达式满足不存在两个连续的加号，且第一个字符和最后一个字符不是加 号，比如 1+01，2+35+8 是合法的表达式，而 +101，23+58+，23++58 不是，表达式 中的数字是十进制的，可以有前导零
高匀想将所有的不同的合法表达式的值都求出来，表达式的值即为这个表达式进行 从左到右的加法运算得到的值，例如表达式 2+3 的值是 5，表达式 02+33 的值是 35
两个表达式不同当且仅当这两个表达式的某一位置的字符不同
因为合法的表达式可能很多，所以高匀只想让你告诉他所有不同合法表达式的值之 和，由于答案可能很大，你只要告诉他答案对 998244353 取模的值即可
输入格式
第一行，两个正整数 n, k，表示字符串长度和加号的数量
第二行一个长度为 n 的字符串，由数字字符 0 ∼ 9 组成
输出格式
一行一个数，表示答案对 998244353 取模的结果
样例
输入数据 1
4 2
2333
输出数据 1
105
不同的合法表达式有 2+3+33,2+33+3,23+3+3
这三个表达式的值分别为 38,38,29，所以答案为 (38+38+29) mod 998244353 = 105
输入数据 2
4 3
2333
输出数据 2
11
数据范围
\(1 \le n \le 5 \times 10^5,0 \le k \le n\)
题解
别人的思路
我的思路
暴力骗分
整场比赛就只有这道题得了分，还好没爆零
当然这篇题解还没完
算法四中说的贡献明显还是要靠我们自己推懒人以后再补
#include<bits/stdc++.h>
#define mod 998244353
#define N 500010
#define int long long
using namespace std;
char s[N];
int f[N],fac[N],inv[N],n,k,ans;
int ksm(int a,int b){
int res = 1;
while(b){
if(b&1) res = res*a%mod;
b>>=1;
a = a*a%mod;
}
return res;
}
int C(int a,int b){
if(a<0||a<b) return 0;
else return ((fac[a]*inv[b])%mod*inv[a-b])%mod;
}
signed main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
fac[0] = 1;
for(int i = 1;i<N;i++) fac[i] = fac[i-1]*i%mod;
inv[N-1] = ksm(fac[N-1],mod-2);
for(int i = N-2;i>=0;i--) inv[i] = inv[i+1]*(i+1)%mod;
scanf("%lld%lld",&n,&k);
cin>>s+1;
for(int i = n-1;i;i--) f[i] = (f[i+1]+ksm(10,n-i-1)*C(i-1,k-1)%mod)%mod;
for(int i = 1;i<=n;i++) f[i] = (f[i]+ksm(10,n-i)*C(i-1,k)%mod)%mod;
for(int i = 1;i<=n;i++) ans = (ans+f[i]*(s[i]-'0')%mod)%mod;
printf("%lld",ans);
return 0;
}
T4 末影龙
题目描述
我的世界中, 基本上所有物体都是由一个个方块构成的。因此, 在这样的世界中考虑曼哈顿距离会 变得非常方便。
考虑一个二维平面直角坐标系, 并给定八个整数 \(a,b,c,d,e,f,g,h\) 。末影龙可能出生在随机的整点 \((x,y)(a≤x≤b,c≤y≤d)\) 处, 它预料到自己将在随机的整点 \((s,t)(e≤s≤f,g≤t≤h)\) 处被 Steve 杀 死。
为了早点投胎变成无忧无虑的小猪, 它将会从 \((x,y)\) 沿着平行于坐标轴的方向尽快到达 \((s,t)\) 。它行 走的路线是一条长度最短的折线, 这条折线的每一段线段都平行于坐标轴, 并且只在整点处拐弯。
对于每一对可能的 \((x,y),(s,t)\), 末影龙都有许多条路线可以选择。请求出每一对 \((x,y),(s,t)\) 之间的 路线数目的和。
保证给定的数字不会使末影龙的出生位置和死亡位置在同一个点, 也就是说, 给定的八个整数确定 的出生点所在的矩形和死亡点所在的矩形没有公共部分。
输入格式
输人文件名为 ender.in。
第一行一个整数 \(T\) 代表数据组数。
接下来 \(T\) 行, 每一行 8 个整数 \(a,b,c,d,e,f,g,h\), 含义见题目描述。
输出格式
输出文件名为 ender.out。
共 \(T\) 行, 每一行一个整数 ans, 代表每一个询问的答案对 666013 (一个质数) 取模后的结果。
样例
输入数据 1
1
0 1 0 1 2 3 2 3
输出数据 1
106
有四个可能的起点，四个可能的终点，任意一个起点到任意一个重点的路线数目的和为 \(10^6\)。
题解
很明显，又要推式子了
但是我们首先需要一个引理 \((a,b)\) 到 \((c,d)\) 的路径数为 \(\tbinom{|a-c|+|b-d|}{|a-c|}\)友情提醒，这个是组合数，与C记号上下颠倒
证明吗……咱不会，自行百度
那么我们考虑一下如何求出一个点到一列点的路径数
左图便是，我们要求的就是红点到蓝色点矩阵的路径数，而蓝色点的加贺可以由组合数递推公式 \(\tbinom{m}{n} = \tbinom{m-1}{m}+\tbinom{m-1}{n-1}\) 得知
方案数等于红点到黄点的路径条数减去红点到粉点的路径条数
右图，红点到蓝点的路径条数也等于到黄点减去到粉点的路径条数，可以根据容斥原理理解
将红色点再扩展为一个矩形后，得到不相交矩形间的基本规律
相交矩形需要另外讨论，此处相交指的是x轴与y轴上都没有相同坐标
两个矩形内的蓝点间的路径条数，等于黄点到黄点的路径条数，加上粉点到粉点的路径条数，减去黄粉点之间的路径条数
对于相交矩形：
先讨论左图，对于AC,AD,BD可以视作3对不相交矩形
BC则可以从中分开进而化为右图
右图中EH,FG不相交而EG与FH之间路径相同，计算随便一边后再乘2即可
#include<bits/stdc++.h>
#define N 200010
#define mod 666013
#define int long long
using namespace std;
int fac[N],inv[N],t;
int ksm(int a,int b){
int ans = 1;
while(b){
if(b&1) ans = ans*a%mod;
a = a*a%mod;
b>>=1;
}
return ans;
}
int C(int a,int b){
a = abs(a);b = abs(b);
return fac[a+b]*inv[a]%mod*inv[b]%mod;
}
int deal(int a,int b,int c,int d,int e,int f,int g,int h){
if(a>c||b>d||e>g||f>h) return 0;
if(e<a){
a = -a;c = -c;
e = -e;g = -g;
}
if(f<b){
b = -b;d = -d;
f = -f;h = -h;
}
if(a>c) swap(a,c);
if(b>d) swap(b,d);
if(e>g) swap(e,g);
if(f>h) swap(f,h);
int res = 0;
res+=C(e-c,f-d);
res+=C(g-c+1,h-d+1);
res+=C(e-a+1,f-b+1);
res+=C(g-a+2,h-b+2);
res+=C(e-c,h-b+2);
res+=C(g-c+1,f-b+1);
res+=C(e-a+1,h-d+1);
res+=C(g-a+2,f-d);
res-=C(e-c,h-d+1);
res-=C(g-c+1,f-d);
res-=C(e-a+1,h-b+2);
res-=C(g-a+2,f-b+1);
res-=C(e-c,f-b+1);
res-=C(g-c+1,h-b+2);
res-=C(e-a+1,f-d);
res-=C(g-a+2,h-d+1);
return (res%mod+mod)%mod;
}
int calc(int a,int b,int c,int d,int h){
if(h==0) return 0;
else if(h&1) return calc(a,b,c,d,h-1)+deal(a,1,b,h-1,c,h,d,h)+deal(a,h,b,h,c,1,d,h-1)+(b-a+1)*(d-c+1)%mod;
else return 2*calc(a,b,c,d,h/2)+2*deal(a,1,b,h/2,c,h/2+1,d,h);
}
signed main(){
freopen("ender.in","r",stdin);
freopen("ender.out","w",stdout);
scanf("%lld",&t);
fac[0] = 1;
for(int i = 1;i<N;i++) fac[i] = fac[i-1]*i%mod;
inv[N-1] = ksm(fac[N-1],mod-2);
for(int i = N-1;i;i--) inv[i-1] = inv[i]*i%mod;
while(t--){
int a,b,c,d,e,f,g,h;
scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&a,&c,&b,&d,&e,&g,&f,&h);
if(a>e){
swap(a,e);swap(c,g);
swap(b,f);swap(d,h);
}
if(e<=c){
swap(a,b);swap(c,d);
swap(e,f);swap(g,h);
}
if(d<=f||h<=b) printf("%lld\n",deal(a,b,c,d,e,f,g,h));
else{
int ans = 0,down = max(b,f),head = min(d,h);
if(d>head) ans+=deal(a,head+1,c,d,e,f,g,h);
if(b<down) ans+=deal(a,b,c,down-1,e,f,g,h);
if(h>head) ans+=deal(e,head+1,g,h,a,down,c,head);
if(f<down) ans+=deal(e,f,g,down-1,a,down,c,head);
ans+=calc(a,c,e,g,head-down+1);
printf("%lld\n",ans%mod);
}
}
return 0;
}
有亿点点难写
总结
这次对于第一题的错极不应该，忘记在正序存储后倒序输出了，导致爆零，而第二题的暴力优化出错是不应该的，第三题与第四题确实难以想到应该下来掌握
标签：10,校内,int,res,字符串,230713,frac,mod From： https://www.cnblogs.com/cztq/p/17555119.html