目录

• A.幼稚园的树
• B.剩下的数
• C.数组划分
• D.子树的大小
• E.剖分

A.幼稚园的树

模拟一下即可，注意第m天中午就是第m-1的最终状态

/*悲观看待成功，乐观看待失败。 author：leimingze 
*/
#include
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=131;
#define YES cout<<"YES"<
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int lcm(int a,int b){return a*b/__gcd(a,b);}
int n;
const int N=1010;
int h[N];
int a,k,b,m;
void solve()
{cin>>n;rep(i,1,n)cin>>h[i];cin>>a>>k>>b;cin>>m;rep(i,1,m-1)rep(j,1,n){h[j]+=a;if(h[j]>k)h[j]=b;}rep(i,1,n)cout<io;int _;_=1;cin>>_;while(_--)solve();return 0;
}

B.剩下的数

区间和为sum
令 y＝sum%x
从l到r挨个%x后 必定有一个数z%x等于y(因为x≤(r-l+1))
(sum-z) % x＝0
则最后只会剩下这个z
上面讨论的是sum%x != 0的情况
sum%x=0直接就0就好了

/*悲观看待成功，乐观看待失败。 author：leimingze 
*/
#include
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=131;
#define YES cout<<"YES"<
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int lcm(int a,int b){return a*b/__gcd(a,b);}
int n;
int l,r;
int m;
void solve()
{cin>>l>>r;cin>>m;int s=(l+r)*(r-l+1)/2;while(m--){int x;cin>>x;if(s%x)cout<<1<io;int _;_=1;cin>>_;while(_--)solve();return 0;
}

C.数组划分

对于A数组分解质因数，然后用数组B的每个元素的质因子看是否在A中能找到

/*悲观看待成功，乐观看待失败。 author：leimingze 
*/
#include
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=131;
#define YES cout<<"YES"<
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int lcm(int a,int b){return a*b/__gcd(a,b);}
int n;
const int N=1e5+10;
int a[N],b[N];
mapmp;
bool get(int x,bool f)
{if(!f){int m=x;rep(i,2,x/i){if(x%i==0){while(x%i==0)x/=i;mp[i]++;}}if(x>1)mp[x]++;}else{rep(i,2,x/i){if(x%i==0){while(x%i==0)x/=i;if(mp.count(i))return false;}}if(x>1&&mp.count(x))return false;}return true;
}
void solve()
{cin>>n;rep(i,1,n)cin>>a[i];rep(i,1,n)cin>>b[i];rep(i,1,n)get(a[i],0);rep(i,1,n){if(!get(b[i],1)){cout<<"No"<io;int _;_=1;//cin>>_;while(_--)solve();return 0;
}

D.子树的大小

题目隐含条件是这棵树是一颗完全二叉树。
那么这道题就可以转换成一道数学题了。
一棵满K叉树的结点个数：(1-k^n)/(1-k)

/*悲观看待成功，乐观看待失败。 author：leimingze 
*/
#include
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=131;
#define YES cout<<"YES"<
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
//int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
//int inv(int a,int mod){return qmi(a,mod-2,mod);}
int lcm(int a,int b){return a*b/__gcd(a,b);}
int qmi(int a, int b){int res = 1;while(b){if(b & 1) res *= a;a *= a;b >>= 1;}return res;}
int n,k,m;
const int N=1e5+10; 
int q[N];
void solve()
{cin>>n>>k>>m;rep(i,1,m)cin>>q[i];rep(i,1,m){if(k==1){cout<hl++;x=x*k+1;}x=(x-1)/k;int y=q[i];int hr=0;while(y<=n-1)y=k*y+k,hr++;y/=(k+1);int res=(qmi(k,hr)-1)/(k-1);if(hrio;int _;_=1;cin>>_;while(_--)solve();return 0;
}

E.剖分

树形差分维护一下即可
注意前缀和时不是回溯，是递归

/*悲观看待成功，乐观看待失败。 author：leimingze 
*/
#include
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=131;
#define YES cout<<"YES"<
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int lcm(int a,int b){return a*b/__gcd(a,b);}
int n,m;
const int N=1e7+10;
int a[N],b[N];
int s[N]; 
int cnt[N];
int dfs(int u,int sum)
{sum+=a[u];if(u*2<=n)s[u]+=dfs(u*2,sum);if(u*2+1<=n)s[u]+=dfs(u*2+1,sum);s[u]=b[u]+sum;return s[u];
}
void solve()
{cin>>n>>m;rep(i,1,m){int op,x;cin>>op>>x;if(op==1)a[x]++;else if(op==2)a[1]++,a[x]--;else if(op==3)while(x>=1)b[x]++,x/=2;else{a[1]++;while(x>=1)b[x]--,x/=2;}}dfs(1,0);rep(i,1,n)cnt[s[i]]++;rep(i,0,m)cout<io;int _;_=1;//cin>>_;while(_--)solve();
}