比赛传送门
邀请码:2024wksyb
A. 简单的数列问题
签到,记得开long long。
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e6+10,M=1e4+10;
LL f[100];
LL calc(int n)
{if(f[n]) return f[n];return f[n]=calc(n-1)+calc(n-2);
}
void Solve()
{f[1]=f[2]=1;int n;cin>>n;cout<<calc(n)<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}
B. 第一次放学
计算每一个班级的人数,贪心的想尽量保留人数较多的,从小到大排序,从小的开始累计即可。
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e5+10,M=1e4+10;
int a[N];
void Solve()
{int n,m,k;cin>>n>>m>>k;rep(i,0,n){int x; cin>>x;++a[x];}sort(a+1,a+1+n);int s=0,mx=0;rep(i,1,n+1){if(s<k){s+=a[i];if(s>k) mx=max(mx,s-k);}else mx=max(mx,a[i]);}cout<<mx<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}
C. 糖果传递
设每一个得到上一个给的值(的为),对下一个的贡献出。注意所有可正可负,负数代表反向给出。记,可以列出下式:
题目转换为求出的最小值,把都用来表示:
问题就是确定,使得数轴上到 n 个点 距离和的最小值,选择其中位数即可。
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e6+10,M=1e4+10;
int a[N];
LL v[N];
void Solve()
{int n; cin>>n;LL s=0,t=0;rep(i,1,n+1) cin>>a[i],s+=a[i];if(n==1){cout<<0<<endl; return;}int b=s/n;rep(i,1,n+1){t+=a[i];if(i==1) v[i]=0;else if(i==n) v[i]=a[1]-b;else v[i]=1ll*(i-1)*b-t+a[1];}sort(v+1,v+1+n);LL ans=0;rep(i,1,n+1) ans+=abs(v[n/2]-v[i]);cout<<ans<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}
D. 矩阵计数
直接计算不好算,考虑用总数
减去不合法数量。
先把所有的点按横坐标小到大排序(相等按纵坐标),于是可以把不和法的情况划分为:枚举 i ,包含以 i 点开头的所有子矩阵个数。这样的算法很方面,只需要保证 i 点与前面节点不包含即可,向前枚举,一段一段的算,卡一下纵坐标的上下界就可以了。
如下图所示,计算以 c 点开头的所有子矩阵个数,保证不包含前面节点,可以分为三段,第一段矩阵左上角选择范围是列值在bc段(不含b),行值比 c 小,右下角为 c 的左下方,如图红色矩阵所示;第二段ab段(不含a)加上了 b 点的限制,右下角列值必须小于 b ,如图中绿色矩阵所示;第三段0a段(不含0),加上 a 点限制,左上角的列值要在ac之间(不含a),如蓝色矩阵所示。通过不断更新左上角和右下角限制,可以设计出一个的算法。
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=1e5+10,M=2e5+10;
pii a[N];
int sfmod(int x,int m=MOD)
{return (x%m+m)%m;
}
void Solve()
{int n,m,k;cin>>n>>m>>k;rep(i,1,k+1) cin>>a[i].fi>>a[i].se;sort(a+1,a+1+k);int ans=1ll*n*(n+1)/2%MOD*(1ll*m*(m+1)/2%MOD)%MOD;rep(i,1,k+1){int l=1,r=m;int res=0;per(j,i-1,-1){int x=1ll*(a[j+1].fi-a[j].fi)*(a[i].se-l+1)%MOD;int y=1ll*(n-a[i].fi+1)*(r-a[i].se+1)%MOD;res=(res+1ll*x*y%MOD)%MOD;if(a[j].se<=a[i].se) l=max(l,a[j].se+1);if(a[j].se>=a[i].se) r=min(r,a[j].se-1);}ans=sfmod(ans-res);}ans=sfmod(ans);cout<<ans<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}
E. 解方程
注意到函数在x > 0 时是单增的,根据零点存在定理二分,稍微调整一下参数 mx 和 eps 即可通过。
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
typedef double db;
using namespace std;
const int MOD=998244353;
const int N=1e7+10,M=1e4+10;
const db eps=1e-5;
db f(db x)
{return 2018*x*x*x*x+21*x+5*x*x*x+5*x*x+14;
}
void Solve()
{db y,l=0,r=100,mx=10000;cin>>y;rep(i,0,mx){db mid=(l+r)/2;if(f(mid)>y) r=mid;else l=mid;}if(abs(f(l)-y)<eps) cout<<fixed<<setprecision(4)<<l<<endl;else cout<<-1<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;cin>>_;while(_--){Solve(); }return 0;
}
F. 随机数
根据二项式定理:
现在要计算 a 的指数为奇数的和,如果 n 是奇数,就可以构造 ,的展开中偶数项的 (-b) 指数 n-i 为奇数,提出负号刚好可以与对应展开项消掉。同理若 n 为偶数,构造即可。
n 很大,但是本题满足模数与底数互素,可以用欧拉降幂提前对 n 做 处理。而且 p-1 是偶数,取模后并不影响原先 n 的奇偶性。
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
typedef double db;
using namespace std;
const int MOD=1e9+7;
const int N=1e7+10;
int qp(int a,int b,int m=MOD)
{int res=1;while(b){if(b&1) res=1ll*res*a%m;a=1ll*a*a%m;b>>=1;}return res%m;
}
int sfmod(int x,int m=MOD)
{return (x%m+m)%m;
}
void Solve()
{int a,n=0; string s;cin>>a>>s;for(auto i:s) n=(1ll*n*10+(int)(i-'0'))%(MOD-1);a=1ll*a*qp(10000,MOD-2)%MOD; int b=sfmod(1-a);int Sum=qp((a+b)%MOD,n),Sub=qp(sfmod(a-b),n),inv2=qp(2,MOD-2),ans=0;if(n&1){ans=1ll*(Sum+Sub)%MOD*inv2%MOD;}else{ans=1ll*sfmod(Sum-Sub)*inv2%MOD;}cout<<ans<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}
G. 【模板】线性筛
复习一下线性筛怎么写,题目问的是第几个素数,数组大小要多开一点。
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e5+10,M=1e7+10;
int pr[N],cnt;
bool st[M];
void INIT()
{int n=1e7;rep(i,2,n+1){if(!st[i]) pr[++cnt]=i;rep(j,1,cnt+1){if(pr[j]*i>n) break;st[i*pr[j]]=1;if(i%pr[j]==0) break;}}
}
void Solve()
{int n;cin>>n;cout<<pr[n]<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;INIT();cin>>_;while(_--){Solve(); }return 0;
}
H. 加解密
如果 S 出现在 a/b 的小数部分中,计算 S*b 和 (S+1)*b 取进位的值可以算出 S 前面的数为,这样可以得到一个范围 [l,r]。计算,如果某一个值在范围内则可以认为 S 出现在了 i+1。
对于 i 比较大的情况,直接枚举会超时。此时可以采用类似于哈希碰撞爆破的思路,a 先计算到 N 的偏移,即 ,计算一个新的范围 [l,r],设置一个宽度 H,向后计算 M 次,将 插入到哈希表中,考虑范围中的每一个值 x,如果出现在了哈希表中即可。对于本题,取,即可通过。
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e6;
LL a,b,c[N+10];
int l,r;
string s;
int gcd(int a,int b)
{while(b^=a^=b^=a%=b);return a;
}
void calc()
{int n=s.size();c[n]=0;rep(i,0,n) c[i]=s[n-i-1]-'0';rep(i,0,n) c[i]*=b;rep(i,0,n) c[i+1]+=c[i]/10,c[i]%=10;int m=n;while(c[m]/10){c[m+1]=c[m]/10; c[m]%=10;++m;}l=0;per(i,m,n-1) l=l*10+c[i];bool fl=0;rep(i,0,n) if(c[i]) fl=1;l+=fl;c[n]=0;rep(i,0,n) c[i]=s[n-i-1]-'0';c[0]+=1;rep(i,0,n) c[i]*=b;rep(i,0,n) c[i+1]+=c[i]/10,c[i]%=10;m=n;while(c[m]/10){c[m+1]=c[m]/10; c[m]%=10;++m;}r=0;per(i,m,n-1) r=r*10+c[i];
}
void Solve()
{cin>>a>>b>>s;int d=gcd(a,b); a/=d;b/=d;a%=b;calc();LL pos=a;rep(i,0,N){if(l<=pos&&pos<=r){cout<<i+1<<endl;return;}pos=pos*10%b;}rep(i,0,N){a*=10; a%=b;int d=gcd(a,b);a/=d; b/=d;}calc();unordered_map<int,int>mp;LL h=1; int H=1000;rep(i,0,H) h=h*10%b;rep(i,1,N){a=a*h%b;if(!mp.count(a)) mp[a]=N+H*i;}int ans=(1<<30);rep(i,l,r+1){LL j=i;rep(_,0,H){if(mp.count(j)) ans=min(ans,mp[j]-_+1);j=j*10%b;}}if(ans==(1<<30)) cout<<-1<<endl;else cout<<ans<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}
I. Treepath
以点 1 为根,求出所有点到 1 的距离,记为 d[i] 。i , j 两个点的距离就是 d[i]+d[j] ,只有同奇偶时和才为偶数,分别统计出奇数距离个数 v1 和偶数距离个数 v0,答案就是。
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e5+10,M=2e5+10;
int d[N];
int h[N],ne[M],e[M],idx;
int v0,v1;
void add(int a,int b)
{e[++idx]=b;ne[idx]=h[a];h[a]=idx;
}
void dfs(int u,int fa)
{if(d[u]&1) ++v1;else ++v0;for(int i=h[u];i;i=ne[i]){int v=e[i];if(v==fa) continue;d[v]=d[u]+1;dfs(v,u);}
}
void Solve()
{int n;cin>>n;rep(i,0,n-1){int a,b;cin>>a>>b;add(a,b);add(b,a);}dfs(1,0);LL ans=1ll*v0*(v0-1)/2+1ll*v1*(v1-1)/2;cout<<ans<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}