Day 6
考试题解
T1 math
签到成功，开心。
看到(T1)第一反应，这啥呀？？？又考数论？？？先打暴力先打暴力。什么？？？暴力都过不了，连暴力都打不出来吗？？？完了完了，签到题不会爆0吧。冷静地分析一波之后，我盲猜这绝对是个结论题，需要推导证明。但考虑到这是签到题，我决定不浪费时间去证明。再次赌神附体，口胡结论，暴力对拍后验证结论后签到成功。题解证明数学结论，然而没听懂，还是不会。
其实暴力打表上几组数据很容易发现规律，实际上就是将指数的最大公因数作为指数，用一个快速幂取模运算求出答案即可。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
ll ksm(ll a1,ll x1,ll p1){
ll ans=1;
while(x1){
if(x1&1) ans=(ans*a1)%p1;
a1=(a1*a1)%p1;
x1>>=1;
}
return ans;
}
ll gcd(ll a,ll b){
if(b==0){
return a;
}
return gcd(b,a%b);
}
ll T,q,a,b,p;
int main()
{
scanf("%lld",&T);
while(T--){
scanf("%lld%lld%lld%lld",&q,&a,&b,&p);
printf("%lld
",(ksm(q,gcd(a,b),p)-1+p)%p);
}
return 0;
}
T2 candy
100分做法：
这个(A)和(B)的数据范围都在1e6以内，暗示选手开桶做。但是我只注意到了单调性，而忘记了使用桶维护，最终还是没能切掉(T2)。
当前弧优化的思想。对于一个A，它找到的B是A的倍数，而且是单调的，所以不需要重新扫描。这样复杂度就是调和级数。总时间复杂度O(nlogn)。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,tot;
int a[1000005],b[1000005],cnt[1000005],t[1000005],f[1000005];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
cnt[b[i]]++;
}
scanf("%d",&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
f[a[i]]=a[i];
}
for(int i=1;i<=n;i++){
int p=f[a[i]];
while(p<=1e6&&!cnt[p]) p+=a[i];
if(p>1e6){
printf("%d
",tot);
for(int j=1;j<=tot;j++){
printf("%d ",t[j]);
}
printf("
");
return 0;
}
tot++;
t[tot]=p;
f[a[i]]=p;
cnt[p]--;
}
return 0;
}
T3 lagrange
结论：
拉格朗日恒等式：sigma a_i^2 * sigma b_i^2 = sigma (a_i*b_i)^2 + sigma(a_ib_j-a_jb_i)
其实不知道结论也能做，随便代入1~3算出结果然后找规律即可，用线段树或树状数组维护即可写出正解。总时间复杂度(O((n+m)logn))。
代码还没调出来QWQ，不知道哪里有问题
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const ll mod=998244353;
ll n,m;
ll a[5000005],b[5000005];
struct Node{
ll v1,v2,v3,v4,v5,tag1,tag2;
int l,r;
Node *ls,*rs;
Node(const int L,const int R){
l=L,r=R;
if(l==r){
tag1=0;
tag2=0;
v1=a[l]*a[l]%mod;//A序列平方和
v2=b[l]*b[l]%mod;//B序列平方和
v3=a[l]*b[l]%mod;//A序列和B序列对应相乘
v4=a[l];//A序列和
v5=b[l];//B序列和
ls=NULL;
rs=NULL;
}
else{
tag1=0;
tag2=0;
int M=(L+R)/2;
ls=new Node(L,M);
rs=new Node(M+1,R);
pushup();
}
}
inline void pushup(){
v1=(ls->v1+rs->v1)%mod;
v2=(ls->v2+rs->v2)%mod;
v3=(ls->v3+rs->v3)%mod;
v4=(ls->v4+rs->v4)%mod;
v5=(ls->v5+rs->v5)%mod;
}
inline void pushdown(){
if(tag1==0&&tag2==0) return;
else{
ls->maketag(tag1,tag2);
rs->maketag(tag1,tag2);
tag1=0;
tag2=0;
}
}
inline void maketag(ll w1,ll w2){
tag1=(tag1+w1)%mod;
tag2=(tag2+w2)%mod;
v3=(v3+v4*w2%mod+v5*w1%mod+(r-l+1)*w1%mod*w2%mod)%mod;
v1=(v1+(r-l+1)*w1%mod*w1%mod+2*w1%mod*v4%mod)%mod;
v2=(v2+(r-l+1)*w2%mod*w2%mod+2*w2%mod*v5%mod)%mod;
v4=(v4+(r-l+1)*w1%mod)%mod;
v5=(v5+(r-l+1)*w2%mod)%mod;//通过公式分别更新，要注意顺序
}
inline bool InRange(const int L,const int R){
return (l>=L)&&(r<=R);
}
inline bool OutofRange(const int L,const int R){
return (l>R)||(r<L);
}
inline void upd(const int L,const int R,ll w1,ll w2){
if(InRange(L,R)){
maketag(w1,w2);
}
else if(!OutofRange(L,R)){
pushdown();
ls->upd(L,R,w1,w2);
rs->upd(L,R,w1,w2);
pushup();
}
}
inline ll qry(const int L,const int R){
if(InRange(L,R)){
return ((v1*v2)%mod+mod-v3*v3%mod+mod)%mod;
}
if(OutofRange(L,R)){
return 0;
}
else{
pushdown();
return (ls->qry(L,R)+rs->qry(L,R))%mod;
}
}
};
int main()
{
n=read();
m=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){
b[i]=read();
}
Node *rot=new Node(1,n);
while(m--){
ll op,x,y,z;
op=read();
x=read();
y=read();
if(op==1){
printf("%lld
",rot->qry(x,y)%mod);
}
else{
z=read();
rot->upd(x,x,y-a[x],z-b[x]);
a[x]=y;
b[x]=z;//奇技淫巧实现单点覆盖，不知道对不对，自己测好像没问题
}
}
return 0;
}
T4 loop
状压dp？
？？？？？？？？？？？？？？？？？？
贪心
没有什么通用技巧，靠感觉做题。猜结论之后对拍证明。
贪心乱搞
求有向图尽量长的简单路径（注意不是最长）。保证存在哈密顿路。N<=100000
？？？？？？？？？？？？？？？？？
匈牙利->一般图最大匹配
DAG和CPU
？？？？？？？？？？？？？？？？？
IOI2020热身赛
？？？？？？？？？？？？？？？？？
Kruskal
CF875F
最大生成环套树森林，因为两个点取一个点的权值，所以如果围成一个环的话那么就正好取完所有点，然后在合并的时候，不能将两个环套树合并，只能将两个树合并或者是一个树和一个环套树合并。
CF1239B
左括号+1，右括号-1，首先手动交换换成合法答案，画成折线图，然后在保证序列合法的前提下，将纵坐标大于2的点之间左右括号交换，相当于-2，出现0点则恰好匹配。
CF1381D
有三个长度大于等于蛇的长度的不同的子树。然后在a->b上的链上不停蠕动，直到找到符合条件的子树。
花
v=1的情况。称花的根为最上面那个点，当v=1时，从下往上贪心即可，能选就选。
？？？？？？？？？？？？？？？？？？？？
黑题
？？？？？？？？？？？？？？？？？？？？
饭
？？？？？？？？？？？？？？？？？？？？
模拟
好题（bushi）：猪国杀，杀蚂蚁
代码能力很重要，调试能力就相当于是推断。
CF1025E
先把棋子移到对角线上，？？？？？？？？？？？？
CF1320F
构造出符合条件的长方体。
二分
二进制分组
比二分更加优秀和优美。
整体二分
？？？？？？？？？？？？？？？？？？
二分斜率
？？？？？？？？？？？？？？？？？？
入门题
二分答案，前缀和后逆序对？？？？？？？？？？？？？？？？？？？？？？？？
经典题
？？？？？？？？？？？？？？？？？？？？？
CF607E
？？？？？？？？？？？？？？？？？？？？？？？？