【题解】2022牛客寒假算法基础集训营2
补题可以看这里
可能有些有我自己的一些宏定义，会显得比较长，大家可以直接看solve部分即可。
K 签到 模拟
#include<iostream>
using namespace std;
int cnt[10];
int main(){
string s;cin>>s;
for(char ch:s)if(ch!='5')cnt[ch-'0']++,cnt[5]++;
for(int i=1;i<=9;i++)cout<<cnt[i]<<" ";
} C 模拟 贪心
#include<iostream>
using namespace std;
int main(){
long long x,a,b;cin>>x>>a>>b;
string s;cin>>s;
int len=0;
for(char ch:s)
if(ch=='1'&&x>=a)len++,x-=a;
else x+=b;
cout<<len;
} E 欧拉图
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
ll n;cin>>n;
if(n&1)cout<<n-1<<" "<<n*(n-1)/2<<"\n";
else cout<<n-1<<" "<<n*(n-1)/2-n/2+1<<"\n";
} H 简单数学
#include<iostream>
using namespace std;
const int mod=1e9+7;
int main(){
long long n,m;
cin>>n>>m;
n%=mod;
long long ans=1;
while(m){
if(m%2==1)ans=ans*n%mod;
m/=2;
}
cout<<ans;
} A 推结论
这里放jls的写法~
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
n = std::min(n, m + 1);
for (int i = 0; i < k; i++) {
long long x;
cin >> x;
long long s = std::sqrt(x);
if (s > n) {
s = n;
}
if (s * (2 * m + s + 1) / 2 >= x)
cout << "YES\n";
else
cout << "NO\n";
}
} I 构造
#include<bits/stdc++.h>
using namespace std;
char ans[10010];
set<char>ft;
int m,n;
char *s="<\\[{(!'*+-.08:=^_WTYUIOAHXVM|\"",*t=">/]})!'*+-.08:=^_WTYUIOAHXVM|\"";
int main(){
cin>>n>>m;
if(m==1)while(n--)putchar(34);
else{
if(n&1)ans[n+1>>1]=34,ft.insert(34);
for(int i=1,ii=n,j=n/2,k=0;j;++i,--ii,--j){
if(ft.size()+1==m)k=max(k,5);
ans[i]=s[k],ans[ii]=t[k];
ft.insert(s[k]),ft.insert(t[k]);
if(ft.size()<m)++k;
k%=30;
}
puts(ft.size()!=m?"-1":ans+1);
}
} F 逆元
#include <bits/stdc++.h>
using namespace std;
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
#define sto \
std::ios::sync_with_stdio(false); \
std::cin.tie(nullptr); \
std::cout.tie(nullptr);
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const double eps=1e-6;
const double PI=acos(-1.0);
inline ll read()
{
char ch;ll x=0;bool f=true;
for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;
return f?x:-x;
}
const int N=1e6+7;
const int mod=1e9+7;
int f[N];
ll s[N],ac[N],res=0;
ll ksm(ll n,ll m){
ll sum=1;
while(n){
if(n&1)sum=sum*m%mod;
m=m*m%mod;
n>>=1;
}
return sum;
}
ll inv(ll m){
return ksm(mod-2,m);
}
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void solve(){
int n=read(),q=read();
string str;cin>>str;str=" "+str;
for(int i=1;i<=n;i++)f[i]=i,ac[i]=s[i]=read(),assert(0<s[i]&&s[i]<mod);
for(int i=1;i<n;i++)if(str[i]=='*'){
int fa=find(i),fb=find(i+1);
f[fa]=fb;
s[fb]=s[fb]*s[fa]%mod;
}
for(int i=1;i<=n;i++)
if(find(i)==i)
res=(res+s[i])%mod;
while(q--){
ll x=read(),y=read();
assert(x<=n);
ll fa=find(x);
res=(res-s[fa]+mod)%mod;
s[fa]=s[fa]*inv(ac[x])%mod;
ac[x]=y;
s[fa]=s[fa]*y%mod;
res=(res+s[fa])%mod;
cout<<res<<"\n";
}
}
int main()
{
//fre("5");
int T=1;
//T=read();
while(T--)solve();
return 0;
}
B 并查集+离散化
#include <bits/stdc++.h>
using namespace std;
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
#define sto \
std::ios::sync_with_stdio(false); \
std::cin.tie(nullptr); \
std::cout.tie(nullptr);
#define pb push_back
#define range(a) a.begin(),a.end()
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const double eps=1e-6;
const double PI=acos(-1.0);
inline ll read(){char ch;ll x=0;bool f=true;for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;return f?x:-x;}
const int N=5e5+7;
int s[N];
vector<int> son[N],ans[N],mp;
void add(int a,int b){son[a].pb(b),son[b].pb(a);}
int fin(int x){return lower_bound(range(mp),x)-mp.begin();}
int f[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void solve(){
ll n=read(),m=read(),res=0,cnt=0;mp.resize(n+1,0);
for(int i=1;i<=n;i++)mp[i]=s[i]=read(),f[i]=i;
sort(range(mp)),mp.erase(unique(range(mp)),mp.end());
for(int i=1;i<=n;i++)ans[fin(s[i])].pb(i);
for(int i=1;i<=m;i++)add(read(),read());
for(int i=mp.size()-1;i;i--){
for(int x:ans[i]){
cnt++;
for(int j:son[x]){
if(s[j]<s[x])continue;
int fa=find(x),fb=find(j);
if(fa!=fb)cnt--,f[fa]=fb;
}
}
res+=(mp[i]-mp[i-1])*cnt;
}
//assert(cnt<=1);
cout<<res;
}
int main(){
int T=1;
//T=read();
//fre("1");
while(T--)solve();
return 0;
}
G LCA+前缀和
#include <bits/stdc++.h>
using namespace std;
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
#define sto \
std::ios::sync_with_stdio(false); \
std::cin.tie(nullptr); \
std::cout.tie(nullptr);
#define pb push_back
#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const double eps=1e-6;
const double PI=acos(-1.0);
inline ll read(){char ch;ll x=0;bool f=true;for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;return f?x:-x;}
const int N=1e6+7;
ll s[N],fac[N],ifac[N];
int f[20][N],h[N];
vector<int> son[N];
void add(int a,int b){son[a].pb(b),son[b].pb(a);}
void dfs(int u,int v,int hh){f[0][u]=v;h[u]=hh;for(int x:son[u])if(x!=v)dfs(x,u,hh+1);}
void cdfs(int u,int v){fac[u]=fac[v];if(s[u]>s[v])fac[u]+=s[u]-s[v];for(int x:son[u])if(x!=v)cdfs(x,u);}
void icdfs(int u,int v){ifac[u]=ifac[v];if(s[u]<s[v])ifac[u]+=s[v]-s[u];for(int x:son[u])if(x!=v)icdfs(x,u);}
int next(int u,int x){for(int i=19;~i;i--)if((1<<i)&x)u=f[i][u];return u;}
int finlca(int u,int v){for(int i=19;~i;i--)if(f[i][u]!=f[i][v])u=f[i][u],v=f[i][v];return f[0][u];}
int lca(int u,int v){if(h[u]<h[v])swap(u,v);u=next(u,h[u]-h[v]);return u==v?v:finlca(u,v);}
void solve(){
int n=read(),q=read();
for(int i=1;i<=n;i++)s[i]=read();
for(int i=1;i<n;i++)add(read(),read());
dfs(1,0,1);
for(int i=1;i<20;i++) for(int j=1;j<=n;j++) f[i][j]=f[i-1][f[i-1][j]];
cdfs(1,0),icdfs(1,0);
while(q--){
int u=read(),v=read(),fa=lca(u,v);
cout<<s[u]+ifac[u]-ifac[fa]+fac[v]-fac[fa]<<"\n";
}
}
int main(){
int T=1;
//fre("10");
while(T--)solve();
return 0;
}
D 数组填数 大模拟
#include <bits/stdc++.h>
using namespace std;
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
#define sto \
std::ios::sync_with_stdio(false); \
std::cin.tie(nullptr); \
std::cout.tie(nullptr);
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const double eps=1e-6;
const double PI=acos(-1.0);
inline ll read()
{
char ch;ll x=0;bool f=true;
for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;
return f?x:-x;
}
const int N=1e3+7;
int s[N][N];
int t[10][10][10];
void dfs(int l,int r,int idx){
int x=r-l+1;
if(x<5){
for(int i=0;i<x;i++)for(int j=0;j<x;j++)
s[l+i][l+j]=t[x][i+1][j+1]+(t[x][i+1][j+1]?idx:0);
return ;
}
else if(x%3==1){
for(int k=0;k<=2;k+=2){
for(int i=l;i<=r-4;i+=3){
s[l+k][i]=s[l+1+k][i]=s[l+k][i+1]=idx++;
s[l+1+k][i+1]=s[l+k][i+2]=s[l+1+k][i+2]=idx++;
s[r-1-k][i+4]=s[r-k][i+4]=s[r-1-k][i+5]=idx++;
s[r-k][i+5]=s[r-1-k][i+6]=s[r-k][i+6]=idx++;
s[i+4][l+k]=s[i+4][l+1+k]=s[i+5][l+k]=idx++;
s[i+5][l+1+k]=s[i+6][l+k]=s[i+6][l+1+k]=idx++;
s[i][r-k]=s[i][r-1-k]=s[i+1][r-k]=idx++;
s[i+1][r-1-k]=s[i+2][r-k]=s[i+2][r-1-k]=idx++;
}
}
dfs(l+4,r-4,idx);
}
else {
for(int i=l;i<=r-3;i+=3){
s[l][i]=s[l+1][i]=s[l][i+1]=idx++;
s[l+1][i+1]=s[l][i+2]=s[l+1][i+2]=idx++;
s[r-1][i+2]=s[r][i+2]=s[r-1][i+3]=idx++;
s[r][i+3]=s[r-1][i+4]=s[r][i+4]=idx++;
s[i+2][l]=s[i+2][l+1]=s[i+3][l]=idx++;
s[i+3][l+1]=s[i+4][l]=s[i+4][l+1]=idx++;
s[i][r]=s[i][r-1]=s[i+1][r]=idx++;
s[i+1][r-1]=s[i+2][r]=s[i+2][r-1]=idx++;
}
dfs(l+2,r-2,idx);
}
}
void solve(){
int n=read();
if(n%3==0)return printf("NO"),void(0);
cout<<"YES"<<"\n";
t[2][1][1]=t[2][1][2]=t[2][2][1]=1;
t[4][1][1]=t[4][1][2]=t[4][2][1]=1;
t[4][4][4]=t[4][3][4]=t[4][4][3]=2;
t[4][1][4]=t[4][1][3]=t[4][2][4]=3;
t[4][4][1]=t[4][4][2]=t[4][3][1]=4;
t[4][2][2]=t[4][2][3]=t[4][3][2]=5;
dfs(1,n,1);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<s[i][j]<<" ";
cout<<"\n";
}
}
int main()
{
int T=1;
//T=read();
while(T--)solve();
return 0;
}
M 树状数组DP
#include<bits/stdc++.h>
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
#define lowit(x) (x&-x)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define sto \
std::ios::sync_with_stdio(false); \
std::cin.tie(nullptr); \
std::cout.tie(nullptr);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> PII;
typedef pair<double,int> PDL;
const int INF=0x3f3f3f3f;
const int base = 131;
const double eps = 1e-6;
const double PI = acos(-1);
#define space putchar(' '),void(0)
#define enter putchar('\n'),void(0)
// <------------------------------->
namespace GenHelper
{
int z1,z2,z3,z4,z5,u,res;
int get()
{
z5=((z1<<6)^z1)>>13;
z1=((int)(z1&4294967)<<18)^z5;
z5=((z2<<2)^z2)>>27;
z2=((z2&4294968)<<2)^z5;
z5=((z3<<13)^z3)>>21;
z3=((z3&4294967)<<7)^z5;
z5=((z4<<3)^z4)>>12;
z4=((z4&4294967)<<13)^z5;
return (z1^z2^z3^z4);
}
int read(int m) {
u=get();
u>>=1;
if(m==0)res=u;
else res=(u/2345+1000054321)%m;
return res;
}
void srand(int x)
{
z1=x;
z2=(~x)^(0x23333333);
z3=x^(0x12345798);
z4=(~x)+51;
u = 0;
}
}
using namespace GenHelper;
const int N=2e6+7,mod=1e9+7;
ll a[N],b[N];
int tr[N],id[N];
void add(int x,ll c){
for(;x<N;x+=lowit(x)){
tr[x]+=c;
if(tr[x]>=mod)tr[x]-=mod;
}
}
ll ask(ll x){
ll res=0;
for(;x;x-=lowit(x))res+=tr[x];
return res-res/mod*mod;
}
void sortID(int n)
{
static const int C = 16, D = 1 << C, mask = D - 1;
static int cnt[D], tmp[N];{
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; i++)
++cnt[a[i] & mask];
for (int i = 1; i < D; i++)
cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i--)
tmp[cnt[a[i] & mask]--] = i;
}
{
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; i++)
++cnt[a[i] >> C];
for (int i = 1; i < D; i++)
cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i--)
id[cnt[a[tmp[i]] >> C]--] = tmp[i];
}
}
int main(){
int n,seed;scanf("%d %d",&n,&seed);
srand(seed);
for(int i=1;i<=n;i++)a[i]=read(0)+2147483648ull,b[i]=read(i),id[i]=i;
sortID(n);
for(int i=1;i<=n;i++){
int c=id[i];
ll x=(ask(c)-ask(c-b[c]-1)+1+mod)%mod;
add(c,x);
}
printf("%lld",ask(n));
return 0;
}
J 线段树维护DDP方程~
#include<bits/stdc++.h>
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
#define lowit(x) (x&-x)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define sto \
std::ios::sync_with_stdio(false); \
std::cin.tie(nullptr); \
std::cout.tie(nullptr);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> PII;
typedef pair<double,int> PDL;
const int INF=0x3f3f3f3f;
const int base = 131;
const double eps = 1e-6;
const double PI = acos(-1);
inline ll read(){
ll x=0;char ch;bool f=true;
for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return f?x:-x;
}
#define space putchar(' '),void(0)
#define enter putchar('\n'),void(0)
void wr(ll x){
if(x<0)putchar('-'),x=-x;
if(x>9)wr(x/10);
putchar(x%10+48);
}
void wr(char *s){
printf("%s",s);
}
// <------------------------------->
const int N=1e5+7;
char ch[11][4]={"","aaa","aac","aab","bbb","bba","bbc","ccc","cca","ccb","abc"};
int w[30][30];
int s[N];
vector<int> node[11];
bool p(int i,const char *s){
int cnt[3]={0};
for(int x=0;x<3;x++,i/=3)cnt[i%3]++,cnt[s[x]-'a']--;
for(int x=0;x<3;x++)if(cnt[x])return false;
return true;
}
void init(){
for(int i=0;i<27;i++)for(int t=1;t<=10;t++)if(p(i,ch[t]))node[t].pb(i);
for(int i=0;i<27;i++)for(int j=0;j<27;j++){
w[i][j]=3;
for(int k=0,c=27;k<3;k++,c/=3)
if(i%c==j*c/27){
w[i][j]=k;
break;
}
}
}
struct T{
int w[6][6];
int ls,rs;
void init(int c){
memset(w,INF,sizeof w);
ls=rs=c;
for(int i=0;i<node[c].size();i++)w[i][i]=0;
}
int money(){
int ans=INF;
for(int i=0;i<node[ls].size();i++)for(int j=0;j<node[rs].size();j++)
ans=min(ans,w[i][j]);
return ans+3;
}
}tr[N<<2];
int a[6][6];
void up(T &v,const T &l,const T &r){
memset(a,INF,sizeof a);
memset(v.w,INF,sizeof v.w);
for(int i=0;i<node[l.ls].size();i++)for(int j=0;j<node[l.rs].size();j++)for(int k=0;k<node[r.ls].size();k++)
a[i][k]=min(a[i][k],l.w[i][j]+w[node[l.rs][j]][node[r.ls][k]]);
for(int i=0;i<node[l.ls].size();i++)for(int j=0;j<node[r.ls].size();j++)for(int k=0;k<node[r.rs].size();k++)
v.w[i][k]=min(v.w[i][k],a[i][j]+r.w[j][k]);
v.ls=l.ls,v.rs=r.rs;
}
#define lson (o<<1)
#define rson (o<<1|1)
#define mid (l+r>>1)
void build(int o,int l,int r){
if(l==r)return tr[o].init(s[l]);
build(lson,l,mid),build(rson,mid+1,r);
up(tr[o],tr[lson],tr[rson]);
}
void add(int o,int l,int r,int X,int c){
if(l==r)return tr[o].init(c);
if(X<=mid)add(lson,l,mid,X,c);
else add(rson,mid+1,r,X,c);
up(tr[o],tr[lson],tr[rson]);
}
T ask(int o,int l,int r,int L,int R){
if(l==L&&R==r)return tr[o];
if(R<=mid)return ask(lson,l,mid,L,R);
else if(L>mid)return ask(rson,mid+1,r,L,R);
T now;
up(now,ask(lson,l,mid,L,mid),ask(rson,mid+1,r,mid+1,R));
return now;
}
void solve(){
int n=read(),m=read();
for(int i=1;i<=n;i++)s[i]=read();
init();
build(1,1,n);
while(m--){
int op=read(),l=read(),r=read();
if(op==1)wr(ask(1,1,n,l,r).money()),enter;
else add(1,1,n,l,r);
}
}
int main(){
#ifdef ONLINE_JUDGE
#else
//fre("1");
#endif
ll T=1;
//T=read();
for(int i=1;i<=T;i++)solve();
}
