正文
Educational Codeforces Round 33 (Rated for Div. 2) 题解
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
A.每个状态只有一种后续转移，判断每次转移是否都合法即可。
#include <iostream>
#include <cstdio>
using namespace std;
int a[], n;
bool check(int x){
if(a[] == x) return false;
int l = a[], r = x, s = -a[]-x;
for(int i = ; i <= n; i++){
if(a[i] == s) return false;
l = a[i]; r = s; s = -l-r;
}
return true;
}int main()
{
cin>>n;
for(int i = ; i <= n; i++) cin>>a[i];
int f = ;
if(check()) f = ;
if(f == ) printf("YES");
else printf("NO");
return ;
}
B.按照题意枚举约数判断即可。
#include <iostream>
using namespace std;
int n;
bool check(int x){
for(int i = ; i <= ; i++){
if( ((<<i) - )*(<<(i-)) == x) return true;
if( ((<<i) - )*(<<(i-)) > x) return false;
}
}
int a[];
int main()
{
int ans = , temp = , last = , L;
cin>>n;
for(int i = ; i <= n; i++){
if(n%i == )
if(check(i))
ans = max(ans, i);
}
cout<<ans<<endl;
}
C.先用并查集并起来，然后瞎搞即可。
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e5 + ;
int a[maxn], f[maxn], v[maxn], s[maxn], M[maxn], x, y;
int find(int x) { return x == f[x] ? f[x] : f[x] = find(f[x]); }
int main()
{
long long ans = ;
int n, m;
cin>>n>>m;
for(int i = ; i <= n; i++){
scanf("%d", &a[i]);
f[i] = i;
v[i] = a[i];
}
for(int i = ; i <= m; i++){
scanf("%d %d", &x, &y);
f[find(x)] = find(y);
}
for(int i = ; i <= n; i++){
v[find(i)] = min(v[find(i)], v[i]);
}
for(int i = ; i <= n; i++){
if(M[find(i)] == ){
M[find(i)] = ;
ans += (long long)v[find(i)];
}
}
cout<<ans<<endl;
}
D.一道题意非常困难的题目orz。
题意大概就是：给你每天的金钱变化，你可以选择加任意数量的钱，但是需要保证每个时刻的钱数不超过d，而且当金钱变化为0时，此时钱的数量必须非负（check一次）
最后还是读错题了。
这道题贪心是对的，先考虑画出价格的折线图。
在第i天加钱，就相当于抬高i天以后的折线。
贪心地想，反正加更多的钱总是更优
所以如果在第i天加钱，就尽量多的加钱
而能加的钱数就是上限d - Max[i](Max为从i到n的后缀)，如果比这个还多，那么后面必定会超
所以就在每个需要加钱的位置都贪心地加钱即可。
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e5 + ;
int a[maxn], n;
long long b[maxn], Max[maxn], d;
int main()
{
cin>>n>>d;
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
b[] = ;
for(int i = ; i <= n; i++) b[i] = b[i-] + a[i];
Max[n] = b[n];
for(int i = n-; i >= ; i--) Max[i] = max(b[i], Max[i+]);
int t = , f = ;
if(Max[] > d){
f = ;
} else {
long long h = ;
for(int i = ; i <= n; i++){
if(a[i] == && b[i] + h < ){
h = d - Max[i];
t++;
if(b[i] + h < ) { f = ; break; }
}
}
}
if(f){
printf("-1");
} else printf("%d", t);
return ;
}
E.给你一个数x，你需要把它拆成y个数的乘积，只要对应位置的yi有一个不同，方案就是不同的，问有多少种方案（负数也算）
首先考虑只有正数。
把x质因数拆分，然后对于每个质因数
你需要把它分配个y个数，比如24 = 3*2^3
其中就需要把3个2分配给y个数，实际上就是y个不同的盒子，3个球，问有多少种方案
答案就是C(y+3-1, y-1)
然后每个质因数乘起来就可以了。
如果是负数，那么其实就是每个正数的方案选出2个变成负数
就是C(n, 0) + C(n, 2) + .... = 2^(n-1)
最后都乘起来就可以了。
这题很蠢的是数组越界了，因为n+m大于1e6，但是没有预处理到（以及找质因数的写法一定要注意）
#include <iostream>
#include <vector>
#include <cstdio>
#define mp make_pair
#define fi first
#define se second
using namespace std;
vector< pair<int, int> > V;
const int MOD = 1e9 + ;
typedef long long LL;
LL f[], invf[];
LL mypow(LL a, LL b){
LL ans = ; for(; b; b >>= , (a *= a) %= MOD) if(b&) (ans *= a) %= MOD; return ans;
}
LL C(LL n, LL m){
return f[n]*invf[m]%MOD*invf[n-m]%MOD;
}
int T, x, y;
int main()
{
cin>>T;
f[] = ;
for(int i = ; i <= ; i++) f[i] = f[i-]*i%MOD;
invf[] = mypow(f[], MOD-);
for(int i = -; i >= ; i--) invf[i] = (invf[i+]*(i+))%MOD;
while(T--){
scanf("%d %d", &x, &y);
int t = x;
long long ans = ;
for(int i = ; i*i <= x; i++){
if(t % i == ){
int temp = ;
while(t % i == ) temp++, t /= i;
(ans *= C(temp+y-, y-) ) %= MOD;
}
}
if(t != ) (ans *= y) %= MOD;
(ans *= mypow(, y-)) %= MOD;
printf("%I64d\n", ans);
}
return ;
}
F.给定一棵树，每次询问x构成的子树内，距离x结点小于等于k的点中值最小的是多少。强制在线
这题我是用可持久化线段树+维护dfs序做的，复杂度是nlogn。不过也有很暴力的线段树维护dfs序nlognlogn做法
具体思想就是可持久化线段树的结点对应是dfs序
插入的时间是按深度排序。
那么询问x，k
就是问插入时间从1~deep[x]+k所构成的树中，x的子树中结点最小的值是多少。
然后维护dfs序，就是查询tree(deep[x] + k, ein[x], eout[x])这个区间的值。
大概就是这样，没什么很坑的地方。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 2e5 + ;
struct Node{
Node *l, *r;
int v;
void maintain(){
v = min(l->v, r->v);
}
}pool[maxn*], *root[maxn], *null;
int pooltot = ;
Node *newnode(){
Node* temp = &pool[pooltot++];
temp->l = temp->r = null; temp->v = 1e9; //
return temp;
}
void init(){
null = new Node();
null->l = null->r = null;
null->v = 1e9; //
}
void Insert(Node *&o, Node *o2, int l, int r, int k, int v){
if(o == null) o = newnode();
if(l == r) { o->v = min(v, o2->v); return; } //
int mid = (l+r)/;
if(k <= mid) {
Insert(o->l, o2->l, l, mid, k, v);
o->r = o2->r;
} else {
Insert(o->r, o2->r, mid+, r, k, v);
o->l = o2->l;
}
o->maintain();
}
int Query(Node *o, int l, int r, int L, int R){
if(o == null) return 1e9; //
if(L <= l && r <= R) return o->v;
int mid = (l+r)/, ans = 1e9; //
if(L <= mid) ans = min(ans, Query(o->l, l, mid, L, R)); //
if(R > mid) ans = min(ans, Query(o->r, mid+, r, L, R)); //
return ans;
}
int tot = , Maxd, timer = ;
int ein[maxn], deep[maxn], eout[maxn], a[maxn], lastd[maxn];
vector<int> D[maxn], G[maxn];
void dfs(int x, int fa, int d){
ein[x] = ++tot;
deep[x] = d;
Maxd = max(d, Maxd);
D[d].push_back(x);
for(auto to : G[x]){
if(to == fa) continue;
dfs(to, x, d+);
}
eout[x] = tot;
}
int n, r, x, y, q;
int main(){
init();
cin>>n>>r;
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
for(int i = ; i < n; i++){
scanf("%d %d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(r, r, );
for(int i = ; i <= n + ; i++) root[i] = newnode();
for(int i = ; i <= Maxd; i++){
for(auto x : D[i]){
Insert(root[timer+], root[timer], , tot, ein[x], a[x]);
timer++;
}
lastd[i] = timer;
}
scanf("%d", &q);
int last = ;
while(q--){
scanf("%d %d", &x, &y);
x = (x+last)%n + ;
y = (y+last)%n;
printf("%d\n", last = Query(root[lastd[min(Maxd, deep[x]+y)]], , tot, ein[x], eout[x]));
}
}
