浙江理工大学2019年5月赛
Problem A 24点
比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=0
补题地址：http://47.96.116.66/problem.php?id=2110
题意：
题解：
按题意模拟即可
用next_permutation()枚举数字的所有排列情况
对于某种排列，用四进制枚举出运算符的所有情况
最后再枚举括号的情况
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[5];
char str;
struct node{};
bool check(){
int A=a[1];
int B=a[2];
int C=a[3];
int D=a[4];
if(A+B+C+D==24)return true;
if(A+B+C-D==24)return true;
if(A+B+C*D==24)return true;
if(A+(B+C)*D==24)return true;
if((A+B+C)*D==24)return true;
if(A+B+C/D==24&&1.0*C/D==C/D)return true;
if(A+(B+C)/D==24&&1.0*(B+C)/D==(B+C)/D)return true;
if((A+B+C)/D==24&&1.0*(A+B+C)/D==(A+B+C)/D)return true;
if(A+B-C+D==24)return true;
if(A+B-C-D==24)return true;
if(A+B-C*D==24)return true;
if(A+(B-C)*D==24)return true;
if((A+B-C)*D==24)return true;
if(A+B-C/D==24&&1.0*C/D==C/D)return true;
if(A+(B-C)/D==24&&1.0*(B-C)/D==(B-C)/D)return true;
if((A+B-C)/D==24&&1.0*(A+B-C)/D==(A+B-C)/D)return true;
if(A+B*C+D==24)return true;
if((A+B)*C+D==24)return true;
if(A+B*(C+D)==24)return true;
if((A+B)*(C+D)==24)return true;
if(A+B*C-D==24)return true;
if((A+B)*C-D==24)return true;
if(A+B*(C-D)==24)return true;
if((A+B)*(C-D)==24)return true;
if(A+B*C*D==24)return true;
if((A+B)*C*D==24)return true;
if(A+B*C/D==24&&1.0*B*C/D==B*C/D)return true;
if((A+B)*C/D==24&&1.0*(A+B)*C/D==(A+B)*C/D)return true;
if((A+B*C)/D==24&&1.0*(A+B*C)/D==(A+B*C)/D)return true;
if(A+B/C+D==24&&1.0*B/C==B/C)return true;
if((A+B)/C+D==24&&1.0*(A+B)/C==(A+B)/C)return true;
if(A+B/(C+D)==24&&1.0*B/(C+D)==B/(C+D))return true;
if((A+B)/(C+D)==24&&1.0*(A+B)/(C+D)==(A+B)/(C+D))return true;
if(A+B/C-D==24&&1.0*B/C==B/C)return true;
if((A+B)/C-D==24&&1.0*(A+B)/C==(A+B)/C)return true;
if(C-D!=0&&A+B/(C-D)==24&&1.0*B/(C-D)==B/(C-D))return true;
if(C-D!=0&&(A+B)/(C-D)==24&&1.0*(A+B)/(C-D)==(A+B)/(C-D))return true;
if(A+B/C*D==24&&1.0*B*D/C==B*D/C)return true;
if((A+B)/C*D==24&&1.0*(A+B)*D/C==(A+B)*D/C)return true;
if(A+B/C/D==24&&1.0*B/C/D==B/C/D)return true;
if((A+B)/C/D==24&&1.0*(A+B)/C/D==(A+B)/C/D)return true;
if(A-B+C+D==24)return true;
if(A-B+C-D==24)return true;
if(A-B+C*D==24)return true;
if(A-(B+C)*D==24)return true;
if((A-B+C)*D==24)return true;
if(A-B+C/D==24)return true;
if(A-(B+C)/D==24&&1.0*(B+C)/D==(B+C)/D)return true;
if((A-B+C)/D==24&&1.0*(A-B+C)/D==(A-B+C)/D)return true;
if(A-B-C+D==24)return true;
if(A-B-C-D==24)return true;
if(A-B-C*D==24)return true;
if(A-(B-C)*D==24)return true;
if((A-B-C)*D==24)return true;
if(A-B-C/D==24)return true;
if(A-(B-C)/D==24&&1.0*(B-C)/D==(B-C)/D)return true;
if((A-B-C)/D==24&&1.0*(A-B-C)/D==(A-B-C)/D)return true;
if(A-B*C+D==24)return true;
if((A-B)*C+D==24)return true;
if(A-B*(C+D)==24)return true;
if((A-B)*(C+D)==24)return true;
if(A-B*C-D==24)return true;
if((A-B)*C-D==24)return true;
if(A-B*(C-D)==24)return true;
if((A-B)*(C-D)==24)return true;
if(A-B*C*D==24)return true;
if((A-B)*C*D==24)return true;
if(A-B*C/D==24)return true;
if((A-B)*C/D==24&&1.0*(A-B)*C/D==(A-B)*C/D)return true;
if((A-B*C)/D==24&&1.0*(A-B*C)/D==(A-B*C)/D)return true;
if(A-B/C+D==24&&1.0*B/C==B/C)return true;
if((A-B)/C+D==24&&1.0*(A-B)/C==(A-B)/C)return true;
if(A-B/(C+D)==24&&1.0*B/(C+D)==B/(C+D))return true;
if((A-B)/(C+D)==24&&1.0*(A-B)/(C+D)==(A-B)/(C+D))return true;
if(A-B/C-D==24&&1.0*B/C==B/C)return true;
if((A-B)/C-D==24&&1.0*(A-B)/C==(A-B)/C)return true;
if(C-D!=0&&A-B/(C-D)==24&&1.0*B/(C-D)==B/(C-D))return true;
if(C-D!=0&&(A-B)/(C-D)==24&&1.0*(A-B)/(C-D)==(A-B)/(C-D))return true;
if(A-B/C*D==24&&1.0*B*D/C==B*D/C)return true;
if((A-B)/C*D==24&&1.0*(A-B)*D/C==(A-B)*D/C)return true;
if(A-B/C/D==24&&1.0*B/C/D==B/C/D)return true;
if((A-B)/C*D==24&&1.0*(A-B)*D/C==(A-B)*D/C)return true;
if(A*B+C+D==24)return true;
if(A*(B+C)+D==24)return true;
if(A*(B+C+D)==24)return true;
if(A*B+C-D==24)return true;
if(A*(B+C)-D==24)return true;
if(A*(B+C-D)==24)return true;
if(A*B+C*D==24)return true;
if(A*(B+C)*D==24)return true;
if(A*(B+C*D)==24)return true;
if((A*B+C)*D==24)return true;
if(A*B+C/D==24&&1.0*C/D==C/D)return true;
if(A*(B+C)/D==24&&1.0*A*(B+C)/D==A*(B+C)/D)return true;
if(A*(B+C/D)==24&&1.0*C/D==C/D)return true;
if((A*B+C)/D==24&&1.0*(A*B+C)/D==(A*B+C)/D)return true;
if(A*B-C+D==24)return true;
if(A*(B-C)+D==24)return true;
if(A*(B-C+D)==24)return true;
if(A*B-C-D==24)return true;
if(A*(B-C)-D==24)return true;
if(A*(B-C-D)==24)return true;
if(A*B-C*D==24)return true;
if(A*(B-C)*D==24)return true;
if(A*(B-C*D)==24)return true;
if((A*B-C)*D==24)return true;
if(A*B-C/D==24)return true;
if(A*(B-C)/D==24&&1.0*A*(B-C)/D==A*(B-C)/D)return true;
if(A*(B-C/D)==24&&1.0*C/D==C/D)return true;
if((A*B-C)/D==24&&1.0*(A*B-C)/D==(A*B-C)/D)return true;
if(A*B*C+D==24)return true;
if(A*B*(C+D)==24)return true;
if(A*B*C-D==24)return true;
if(A*B*(C-D)==24)return true;
if(A*B*C*D==24)return true;
if(A*B*C/D==24&&1.0*A*B*C/D==A*B*C/D)return true;
if(A*B/C+D==24&&1.0*A*B/C==A*B/C)return true;
if(A*B/(C+D)==24&&1.0*A*B/(C+D)==A*B/(C+D))return true;
if(A*B/C-D==24&&1.0*A*B/C==A*B/C)return true;
if(C-D!=0&&A*B/(C-D)==24&&1.0*A*B/(C+D)==A*B/(C-D))return true;
if(A*B/C*D==24&&1.0*A*B*D/C==A*B*D/C)return true;
if(A*B/C/D==24&&1.0*A*B/C/D==A*B/C/D)return true;
if(A/B+C+D==24&&1.0*A/B==A/B)return true;
if(A/(B+C)+D==24&&1.0*A/(B+C)==A/(B+C))return true;
if(A/(B+C+D)==24&&1.0*A/(B+C+D)==A/(B+C+D))return true;
if(A/B+C-D==24)return true;
if(A/(B+C)-D==24&&1.0*A/(B+C)==A/(B+C))return true;
if(B+C-D!=0&&A/(B+C-D)==24&&1.0*A/(B+C-D)==A/(B+C-D))return true;
if(A/B+C*D==24&&1.0*A/B==A/B)return true;
if(A/(B+C)*D==24&&1.0*A*D/(B+C)==A*D/(B+C))return true;
if(A/(B+C*D)==24&&1.0*A/(B+C*D)==A/(B+C*D))return true;
if(A/B+C/D==24&&1.0*A/B==A/B&&1.0*C/D==C/D)return true;
if(A/(B+C)/D==24&&1.0*A/(B+C)/D==A/(B+C)/D)return true;
if(A/(B+C/D)==24&&1.0*C/D==C/D&&1.0*A/(B+C/D)==A/(B+C/D))return true;
if((A/B+C)/D==24&&1.0*A/B==A/B&&1.0*(A/B+C)/D==(A/B+C)/D)return true;
if(A/B-C+D==24&&1.0*A/B==A/B)return true;
if(B-C!=0&&A/(B-C)+D==24&&1.0*A/(B-C)==A/(B-C))return true;
if(B-C+D!=0&&A/(B-C+D)==24&&1.0*A/(B-C+D)==A/(B-C+D))return true;
if(A/B-C-D==24&&1.0*A/B==A/B)return true;
if(B-C!=0&&A/(B-C)-D==24&&1.0*A/(B-C)==A/(B-C))return true;
if(B-C-D!=0&&A/(B-C-D)==24&&1.0*A/(B-C-D)==A/(B-C-D))return true;
if(A/B-C*D==24&&1.0*A/B==A/B)return true;
if(B-C!=0&&A/(B-C)*D==24&&1.0*A*D/(B-C)==A*D/(B-C))return true;
if(B-C*D!=0&&A/(B-C*D)==24&&1.0*A/(B-C*D)==A/(B-C*D))return true;
if(A/B-C/D==24&&1.0*A/B==A/B&&1.0*C/D==C/D)return true;
if(B-C!=0&&A/(B-C)/D==24&&1.0*A/(B-C)/D==A/(B-C)/D)return true;
if(B-C/D!=0&&A/(B-C/D)==24&&1.0*C/D==C/D&&1.0*A/(B-C/D)==A/(B-C/D))return true;
if((A/B-C)/D==24&&1.0*A/B==A/B&&1.0*(A/B-C)/D==(A/B-C)/D)return true;
if(A/B*C+D==24&&1.0*A*C/B==A*C/B)return true;
if(A/(B+C)*D==24&&1.0*A*D/(B+C)==A*D/(B+C))return true;
if(A/(B+C*D)==24&&1.0*A/(B+C*D)==A/(B+C*D))return true;
if(A/B*C-D==24&&1.0*A*C/B==A*C/B)return true;
if(A/B*(C-D)==24&&1.0*A*(C-D)/B==A*(C-D)/B)return true;
if(B*C-D!=0&&A/(B*C-D)==24&&1.0*A/(B*C-D)==A/(B*C-D))return true;
if(A/B*C*D==24&&1.0*A*C*D/B==A*C*D/B)return true;
if(A/B*C/D==24&&1.0*A*C/B/D==A*C/B/D)return true;
if(A/B/C+D==24&&1.0*A/B/C==A/B/C)return true;
if(A/B/(C+D)==24&&1.0*A/B/(C+D)==A/B/(C+D))return true;
if(A/B/C-D==24&&1.0*A/B/C==A/B/C)return true;
if(C-D!=0&&A/B/(C-D)==24&&1.0*A/B/(C-D)==A/B/(C-D))return true;
if(A/B/C*D==24&&1.0*A*D/B/C==A*D/B/C)return true;
if(A/B/C/D==24&&1.0*A/B/C/D==A/B/C/D)return true;
return false;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d%d%d%d",&a[1],&a[2],&a[3],&a[4]);
ans=0;
while(cnt<24){
++cnt;
next_permutation(a+1,a+5);
if(check()){ans=1;break;}
}
cout<<(ans?"Yes":"No")<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem B Pikachu
比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=1
补题地址：http://47.96.116.66/problem.php?id=2111
题意：
第一种操作对[l,r]区间内每幢房子塞入一个皮卡丘; 第二种操作对第l次到第r次的操作重复一遍。
问依次进行m次操作后每幢房子内皮卡丘的个数。
题解：
可以 O(n)维护两个差分数组，一个是针对重复操作的差分数组，一个是针对当前房子塞入皮卡丘的个数的差分数组。对第二个差分数组的每次修改的大小是当前操作重复操作次数。 因为每一次第二种操作总是针对之前的操作，所以要倒着跑一遍。 最后对针对当前房子塞入皮卡丘的个数的差分数组求个前缀和就好了。
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
ll a[N],pre[N];
char str;
struct node{
int l,r,op;
}e[N];
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
memset(pre,0,sizeof(pre));
memset(a,0,sizeof(a));
pre[m+1]++;
pre[0]--;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&e[i].op,&e[i].l,&e[i].r);
}
for(int i=m;i>=1;i--){
pre[i]=(pre[i]+pre[i+1])%MOD;
if(e[i].op!=1){
pre[e[i].r]=(pre[e[i].r]+pre[i])%MOD;
pre[e[i].l-1]=(pre[e[i].l-1]-pre[i]+MOD)%MOD;
}else{
a[e[i].l]=(a[e[i].l]+pre[i])%MOD;
a[e[i].r+1]=(a[e[i].r+1]-pre[i]+MOD)%MOD;
//cout<<e[i].l<<" "<<e[i].r<<" "<<pre[i]<<endl;
}
}
for(int i=1;i<=n;i++){
a[i]=(a[i]+a[i-1])%MOD;
}
for(int i=1;i<=n;i++){
printf("%lld%c",a[i]," \n"[i==n]);
}
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem C Raichu
比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=2
补题地址：http://47.96.116.66/problem.php?id=2112
题意：
第一种操作对第x幢房子塞入一个吕子乔; 第二种操作对第x次操作重复一遍。
问依次进行m次操作后每幢房子内吕子乔的个数（初始每幢房子都是空的）。
题解：根据题意可以得出结论一个第二种操作回溯到头一定是第一种操作,一定是一个链状的结构。 同时我们很容易维护每个第二种操作的头节点是谁,可以通过直接继承前一次操作的头节点
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N],pre[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
if(u==1){
a[v]++;
pre[i]=v;
}else{
pre[i]=pre[v];
a[pre[v]]++;
}
}
for(int i=1;i<=n;i++){
printf("%d%c",a[i]," \n"[i==n]);
}
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem D 本题不用算法
比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=3
补题地址：http://47.96.116.66/problem.php?id=2113
题意：给你三个数Ａ，Ｂ，Ｃ，你需要找到另外三个数ａ，ｂ，ｃ分别是对应Ａ，Ｂ，Ｃ的因数，请你输出一共有多少种方案数（三个数顺序改变视为同一种方案）
题解：容斥+组合数学+状态压缩
无非只有7种状况
001：只是A的约数，不是BC的约数，这是可以容斥的。下同。
010：只是B的因数。
100：只是C的因数。
011：只是AB的因数。
101：只是AC的因数。
110：只是BC的因数。
111：同时是ABC的因数
我们现在就可以枚举每条边的状态了，三重循环7*7*7次。那么接下来我们考虑什么样的边是满足条件的边呢：
给小长方体一个合适的翻转，使三条边至少分别是ABC点的因子。怎么做呢？上面我们按位处理了每条边的状态，所以只要没枚举一下变得顺序（翻转正方形）使得和ABC一一对应（对应位为1）
bool check(int a,int b,int c){
if((a&1) && (b&2) && (c&4))
return true;
if((a&1) && (c&2) && (b&4))
return true;
if((b&1) && (a&2) && (c&4))
return true;
if((b&1) && (c&2) && (a&4))
return true;
if((c&1) && (a&2) && (b&4))
return true;
if((c&1) && (b&2) && (a&4))
return true;
return false;
}
好了接下来我们找到合适的三边了，那么怎么计算此时的种类呢？这也是本体的一大亮点。
1.如果a，b，c是不同的状态得来的，那么ok没有重复。每种数量选一个，也就是乘起来就好啦~
2.但是如果有两个数或者三个数是相同的状态，这就要求我们从一定数量中选择有重复个元素。举个例子，如果ab状态相同，都是cond[s]，那么我们应该从cond[s]中选两个，并且可以重复即a选了k，b也选了k
这就需用到有重复的组合公式：
如果从n个元素中选择r个有重复元素，其公式为：
另外，我们用use数组将计算过程一般化，use[i]即为r。请好好体会。这里非常巧妙。
C++版本一
#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 10;
int fac[maxn];
void fac_table(int n){
for(int i = 1;i < n;i++)
for(int j = i;j < n;j+=i)
fac[j]++;
return;
}
ll C(int n,int m){
ll ans = 1;
for(int i = 1;i <= m;i++){
ans = ans*(n-i+1)/i;
}
return ans;
}
int gcd(int a,int b){
if(b == 0)
return a;
return gcd(b,a%b);
}
bool check(int a,int b,int c){
if((a&1) && (b&2) && (c&4))
return true;
if((a&1) && (c&2) && (b&4))
return true;
if((b&1) && (a&2) && (c&4))
return true;
if((b&1) && (c&2) && (a&4))
return true;
if((c&1) && (a&2) && (b&4))
return true;
if((c&1) && (b&2) && (a&4))
return true;
return false;
}
int condi[10],use[10];
int main(){
fac_table(maxn);
ll T;
int x,y,z;ll ans;
scanf("%lld",&T);
while(T--){
scanf("%d%d%d",&x,&y,&z);
int xy = gcd(x,y);
int xz = gcd(x,z);
int yz = gcd(y,z);
int xyz = gcd(xy,z);
condi[1] = fac[x] - fac[xy] - fac[xz] + fac[xyz];//001
condi[2] = fac[y] - fac[xy] - fac[yz] + fac[xyz];//010
condi[4] = fac[z] - fac[xz] - fac[yz] + fac[xyz];//100
condi[3] = fac[xy] - fac[xyz];//011
condi[5] = fac[xz] - fac[xyz];//101
condi[6] = fac[yz] - fac[xyz];//110
condi[7] = fac[xyz];
ans = 0;
for(int a = 1;a < 8;a++)
for(int b = a;b < 8;b++)
for(int c = b;c < 8;c++)
if(check(a,b,c) == true){
memset(use,0,sizeof(use));
use[a]++;use[b]++;use[c]++;
ll tmp = 1;
for(int i = 1;i < 8;i++)
if(use[i] != 0)
tmp = tmp*C(condi[i] + use[i]-1,use[i]);
if(tmp > 0)
ans += tmp;
}
printf("%lld\n",ans);
}
return 0;
}
Problem E 博弈
比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=4
补题地址：http://47.96.116.66/problem.php?id=2114
题意：小A和小B进行一场博弈，有一个串有n颗珠子的圆环，每次一个人可以取走连续的1颗或2颗，问谁会赢。
题解：如果是1或2，那么小A取走直接赢，否则小B赢，因为他可以变成对称博弈。
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d",&n);
cout<<(n==1||n==2?'A':'B')<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem F 地下迷宫
比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=5
补题地址：http://47.96.116.66/problem.php?id=2115
题意：任意两点之间最短路
题解：先建成一颗生成树，然后对于剩下的边的所有点跑一边最短路，记录下这些点到其他所有点的距离，然后跑树上最短路，再暴力枚举剩下的边，取距离最小值。
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v,w;
ll ans,cnt,flag,temp,sum;
int dp[23][N];
ll dis[N];
ll dep[N];
int pre[N];
bool vis[N];
ll dist[30][N];
int tag[N];
char str;
struct node{
int u,v;
ll w;
bool vis;
node(){ };
node(int u,int v ,ll w):u(u),v(v),w(w),vis(0){ }
bool operator <(const node &S)const{
return w<S.w;
}
}e[N],tmp[30];
int find(int x){return pre[x]==x?x:pre[x]=find(pre[x]);}
vector<node>G[N];
void dfs(int u){
vis[u]=1;
for(int i=0,j=G[u].size();i<j;i++){
int v=G[u][i].v;
if(vis[v]==0){
dp[0][v]=u;
dep[v]=dep[u]+1;
dis[v]=dis[u]+G[u][i].w;
dfs(v);
}
}
}
int LCA(int x,int y){
if(dep[x]<dep[y])
swap(x,y);
while(dep[x]>dep[y]){
x=dp[(int)log2(dep[x]-dep[y])][x];
}
if(x==y)
return x;
for(int i=log2(dep[x]);i>=0;i--){
if(dp[i][x]!=dp[i][y]){
x=dp[i][x];
y=dp[i][y];
}
}
return dp[0][x];
}
void spfa(int u,ll *dist){
memset(vis,0,sizeof(vis));
dist[u]=0;
queue<int>q;
q.push(u);
vis[u]=1;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=0,j=G[u].size();i<j;i++){
node e=G[u][i];
if(dist[e.v]>dist[u]+e.w){
dist[e.v]=dist[u]+e.w;
if(vis[e.v]==0){
q.push(e.v);
vis[e.v]=1;
}
}
}
}
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)pre[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w);
}
sort(e+1,e+m+1);
for(int i=1;i<=m;i++){
u=e[i].u;
v=e[i].v;
w=e[i].w;
int tx=find(u);
int ty=find(v);
if(tx!=ty){
pre[tx]=ty;
e[i].vis=1;
G[u].push_back({u,v,w});
G[v].push_back({v,u,w});
}else{
tmp[++sum]=e[i];
}
}
for(int i=1;i<=n;i++){
if(vis[i]==0)dfs(i);
}
for(int i=0;i<22;i++){
for(int j=1;j<=n;j++){
dp[i+1][j]=dp[i][dp[i][j]];
}
}
for(int i=1;i<=sum;i++){
if(tmp[i].vis==0){
u=tmp[i].u;
v=tmp[i].v;
w=tmp[i].w;
G[u].push_back({u,v,w});
G[v].push_back({v,u,w});
}
}
memset(dist,0x3f,sizeof(dist));
for(int i=1;i<=sum;i++){
if(tmp[i].vis==0){
if(tag[tmp[i].u]==0){
tag[tmp[i].u]=++cnt;
spfa(tmp[i].u,dist[cnt]);
}
if(tag[tmp[i].v]==0){
tag[tmp[i].v]=++cnt;
spfa(tmp[i].v,dist[cnt]);
}
}
}
scanf("%d",&k);
while(k--){
scanf("%d%d",&u,&v);
ans=dis[u]+dis[v]-2*dis[LCA(u,v)];
for(int i=1;i<=sum;i++){
ll x=dist[tag[tmp[i].u]][u];
ll y=dist[tag[tmp[i].v]][v];
ans=min(ans,x+y+tmp[i].w);
x=dist[tag[tmp[i].u]][v];
y=dist[tag[tmp[i].v]][u];
ans=min(ans,x+y+tmp[i].w);
}
cout<<ans<<endl;
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem G 简简单单的数学题
比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=6
补题地址：http://47.96.116.66/problem.php?id=2116
题意：⌊a⌋ +⌈b⌉+c(四舍五入)+d^n
题解：快速幂+乘法优化
C++版本一
题解：快速幂+__int128
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const ll MOD=1e12;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
double a,b,c;
ll d;
char str;
struct node{};
ll POW(ll a,ll b,ll c){
__int128 res=1;
__int128 base=a%c;
while(b){
if(b&1)res=(res*base)%c;
base=(base*base)%c;
b>>=1;
}
return res;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
//scanf("%d",&n);
scanf("%lf%lf%lf",&a,&b,&c);
ll A=a;
ll B=b;
if(b-B>0)B++;
ll C=c+0.5;
scanf("%lld",&k);
while(k--){
scanf("%lld%lld",&d,&n);
printf("%lld\n",(((A+B)%MOD+C)%MOD+POW(d,n,MOD))%MOD);
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
快速幂+乘法优化，变成1e6进制的数
Problem H 拼可可
比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=7
补题地址：http://47.96.116.66/problem.php?id=2117
题意：至少多少个a*b的矩形才能拼成一个正方形？
题解：求a，b的lcm即可
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%lld%lld",&n,&m);
ll gcd=__gcd(n,m);
printf("%lld\n",(n/gcd)*(m/gcd));
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem I 签到题
比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=8
补题地址：http://47.96.116.66/problem.php?id=2118
题意：
题解：二分答案，差分检查。
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v,w;
int ans,cnt,flag,temp,sum;
int a[N],b[N];
char str;
struct node{};
bool sloved(int mid){
memset(b,0,sizeof(b));
sum=0;
for(int i=1;i<=n;i++){
b[i]+=b[i-1];
if(a[i]+b[i]<mid){
int temp=mid-a[i]-b[i];
b[i]+=temp;
b[min(n+1,i+w)]-=temp;
sum+=temp;
}
}
return sum<=m;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&w);
int l=INF;
int r=-INF;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
l=min(l,a[i]);
r=max(r,a[i]+m);
}
while(l<=r){
int mid=(l+r)>>1;
if(sloved(mid)){
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
cout<<ans<<endl;
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem J 无尽递增
比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=9
补题地址：http://47.96.116.66/problem.php?id=2119
题意：找一个最长的子序列，1111122222.
题解：DP
转化题意后，其实就是找出最长的1111222211112222，我们可以开dp【4】，分别表示以红色标出的值为结尾的最长子序列。
转移公式为：
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N],dp[5];
char str;
struct node{};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
scanf("%d",&t);
while(t--){
scanf("%d",&n);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
dp[1]=dp[1]+(a[i]==1);
dp[2]=max(dp[1],dp[2]+(a[i]==2));
dp[3]=max(dp[2],dp[3]+(a[i]==1));
dp[4]=max(dp[3],dp[4]+(a[i]==2));
}
cout<<dp[4]<<endl;
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem K 消消乐
比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=10
补题地址：http://47.96.116.66/problem.php?id=2120
题意：
题解：区间dp + 记忆化搜索
dp[i][j][k] : （区间 [i, j] 后面带上一段和 j 颜色相同的且长度为 k ）的消消乐最大积分
1.消最后一段颜色和 j 颜色相同的
dp[i][j][k] <-- dp[i][j-1][0] + (k+1)^3
2.对于i <= l < j， 如果 l 和 j 的颜色相同， 那么可以把 [l+1, j-1]消掉, 那么剩下的一段就有 k+1 个和 l 相同的一段了
dp[i][j][k] <-- dp[i][l][k+1] + dp[l+1][j-1][0]
答案就是dp[1][n][0]，采用记忆化搜索更方便转移
C++版本一
Problem L 寻宝
比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=11
补题地址：http://47.96.116.66/problem.php?id=2121
题意：
题解：
Exkmp预处理出数组，后缀数组也行，查询由于强制在线主席树顺便搞搞就好，对于会这两个算法的人这题应该是一道一眼题，而且由于懒得造数据，所以数据都是循环的，说不定有什么优秀的暴力也能过
C++版本一
Problem M 智慧爷的蛋糕
比赛地址：http://47.96.116.66/problem.php?cid=1275&pid=12
补题地址：http://47.96.116.66/problem.php?id=2122
题意：求后缀子串的最长公共前缀子串
题解：SA+LCP+ST
(方法一) 后缀数组 ST表预处理 复杂度 nlogn
(方法二) 字符串哈希+二分 qlog(n)+n
C++版本一
题解：后缀数组 ST表预处理
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,u,v,q;
int ans,cnt,flag,temp,sum;
char str[N];
/*
da(str ,sa,rank,height,n ,128);//n是字符串长度;
*例如：
*n = 8，实际元素有9个，最后加上一个$ (即最小字符)
*num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位为0，其他大于0
*rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]为有效值，rank[n]必定为0无效值
*sa[]= { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]为有效值，sa[0]必定为n是无效值
*height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值
*/
int t1[N],t2[N],c[N];//求SA数组需要的中间变量，不需要赋值
//待排序的字符串放在s数组中，从s[0]到s[n-1],长度为n,且最大值小于m,
//除s[n-1]外的所有s[i]都大于0，r[n-1]=0
//函数结束以后结果放在sa数组中,sa数组下标范围1~n
bool cmp(int *r,int a,int b,int l) {
return r[a] == r[b] && r[a+l] == r[b+l];
}
void da(int str[],int sa[],int rank1[],int height[],int n,int m) { //n是串长度，m是字符集大小，一般128
n++;
int i, j, p, *x = t1, *y = t2;
//第一轮基数排序，如果s的最大值很大，可改为快速排序
for(i = 0; i < m; i++)c[i] = 0;
for(i = 0; i < n; i++)c[x[i] = str[i]]++;
for(i = 1; i < m; i++)c[i] += c[i-1];
for(i = n-1; i >= 0; i--)sa[--c[x[i]]] = i;
for(j = 1; j <= n; j <<= 1) {
p = 0;
//直接利用sa数组排序第二关键字
for(i = n-j; i < n; i++)y[p++] = i;//后面的j个数第二关键字为空的最小
for(i = 0; i < n; i++)if(sa[i] >= j)y[p++] = sa[i] - j;
//这样数组y保存的就是按照第二关键字排序的结果
//基数排序第一关键字
for(i = 0; i < m; i++)c[i] = 0;
for(i = 0; i < n; i++)c[x[y[i]]]++;
for(i = 1; i < m; i++)c[i] += c[i-1];
for(i = n-1; i >= 0; i--)sa[--c[x[y[i]]]] = y[i];
//根据sa和x数组计算新的x数组
swap(x,y);
p = 1;
x[sa[0]] = 0;
for(i = 1; i < n; i++)
x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;
if(p >= n)break;
m = p;//下次基数排序的最大值
}
int k = 0;
n--;
for(i = 0; i <= n; i++)rank1[sa[i]] = i;
for(i = 0; i < n; i++) {
if(k)k--;
j = sa[rank1[i]-1];
while(str[i+k] == str[j+k])k++;
height[rank1[i]] = k;
}
}
int rank1[N],height[N];
int RMQ[N];
int mm[N];
int best[23][N];
void initRMQ(int n) { //调用da后，初始化RMQ（求LCP用）
for(int i=1;i<=n;i++)RMQ[i]=height[i];
mm[0]=-1;
for(int i=1; i<=n; i++)
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
for(int i=1; i<=n; i++)best[0][i]=i;
for(int i=1; i<=mm[n]; i++)
for(int j=1; j+(1<<i)-1<=n; j++) {
int a=best[i-1][j];
int b=best[i-1][j+(1<<(i-1))];
if(RMQ[a]<RMQ[b])best[i][j]=a;
else best[i][j]=b;
}
}
int askRMQ(int a,int b) {
int t;
t=mm[b-a+1];
b-=(1<<t)-1;
a=best[t][a];
b=best[t][b];
return RMQ[a]<RMQ[b]?a:b;
}
int lcp(int a,int b) {
a=rank1[a];
b=rank1[b];
if(a>b)swap(a,b);
return height[askRMQ(a+1,b)];
}
int r[N]; //把字符串存到这个数组里
int sa[N]; //后缀数组
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d",&n);
cin>>str;
for(int i=0;i<n;i++)
r[i]=str[i];
r[n]='$';
da(r,sa,rank1,height,n,128);
initRMQ(n);
scanf("%d",&q);
int a,b,c,d;
while(q--){
scanf("%d%d%d%d",&a,&b,&c,&d);
cout<<(a==c?min(b-a+1,d-c+1):min(min(b-a+1,d-c+1),lcp(a,c)))<<endl;
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
小红书公司福利 641人发布