宁波seo推广哪家公司好_小程序开发定制公司北京_线下推广的渠道和方法_百度网页版

Codeforces Global Round 27https://codeforces.com/contest/2035

A. Sliding

先算跨行填补的：从 r+1 行开始每一行第一个会填补到上一行最后一个，距离为 m，这些总距离就是 (n-r)*m

再算距离为 1 的：第 r 行的 m-c 个，r+1 行开始后面每行 m-1 个，总共就是 (n-r)*(m-1)+m-c

//#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;
typedef double db;
const int MOD=998244353;
const int N=1e5+10;inline void Solve()
{int n,m,a,b;cin>>n>>m>>a>>b;LL ans=(LL)(n-a)*(m-1)+(LL)m*(n-a)+m-b;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;
}

B. Everyone Loves Tres

十进制数可以写成 $\sum a_i*10^i$ 的形式，本题 $a_i = 3,6$ ，只需要求满足 $\sum a_i *10^i \pmod {66} =0$ 的最小值。

打表出 $10^i \pmod{66}$ 的结果：

10^0 mod 66 = 1
10^1 mod 66 = 10
10^2 mod 66 = 34
10^3 mod 66 = 10
10^4 mod 66 = 34
10^5 mod 66 = 10
10^6 mod 66 = 34
10^7 mod 66 = 10
10^8 mod 66 = 34
10^9 mod 66 = 10
10^10 mod 66 = 34
10^11 mod 66 = 10
10^12 mod 66 = 34
10^13 mod 66 = 10
10^14 mod 66 = 34
10^15 mod 66 = 10
10^16 mod 66 = 34
10^17 mod 66 = 10
10^18 mod 66 = 34
10^19 mod 66 = 10

可以发现后面结果都是10和34循环了，而且注意到有 $3\cdot 10 + 3 \cdot 34 \pmod {66} =0$ 成立，所以对于偶数的情况就是最低两位填 66，高位全部填 3；奇数的情况就是不足5位不满足，否则最低 5 位填 36366，高位全部填 3。

//#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;
typedef double db;
const int MOD=998244353;
const int N=1e5+10;inline void Solve()
{int n;cin>>n;if(n&1){if(n<=3) cout<<-1<<endl;else{rep(i,0,n-5) cout<<'3';cout<<"36366"<<endl;}}else{rep(i,0,n-2) cout<<'3';cout<<"66"<<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. Alya and Permutation

把整个过程看做逆向操作来确定 k，或操作的 1 位可以确定为 1，与操作的 0 位可以确定为 0。对于偶数，可以构造 1000，0111，0100，0011.... 最后可以把 k 所有位都变成 1；对于奇数的情况，因为首先进行与操作，为了保证结果最大选择 n，后面按照偶数的策略保证把其他的位确定为 1。（n=5 除外，因为按照该算法 1~4 只能凑出 110）

下面是 n=10 和 n=9 的例子帮助理解：

//#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;
typedef double db;
const int MOD=998244353;
const int N=2e5+10;
int p2[25];
unordered_set<int>st;
void INIT()
{p2[0]=1;st.emplace(1);rep(i,1,21) p2[i]=p2[i-1]*2,st.emplace(p2[i]);
}
void outp(int n,vector<int>&a)
{int t=0,k=0;while(p2[t]<=n) ++t;--t;per(i,t,0) a.emplace_back(p2[i]),a.emplace_back(p2[i]-1);for(int i=6;i<=n;i+=2) if(!st.count(i)) a.emplace_back(i-1),a.emplace_back(i);reverse(all(a));rep(i,0,(int)a.size()){if(i&1) k|=a[i];else k&=a[i];}cout<<k<<endl;for(auto it:a) cout<<it<<" ";cout<<endl;
}
inline void Solve()
{vector<int>a;int n;cin>>n;if(n==5){cout<<5<<endl;cout<<"2 1 3 4 5"<<endl;return; }if(n&1){a.emplace_back(n);outp(n-1,a);}else outp(n,a);}
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;
}

D. Yet Another Real Number Problem

考虑一个固定的数组 a 通过题目操作把和变到最大：逆序遍历数组，维护当前最大的数，如果遇到偶数就把 2 乘到这个最大的数上。基于这个思路，就可以用数对来表示每一个数，(a, b) 表示 $2^a \cdot b$ ，b 为奇数，每当增加一个数的时候，如果前面数对中 b 的值比新的 $2^a \cdot b$ 的值要小，说明把前面的 2 乘到新的数对上更优，更新数对和答案即可，这样就维护出了一个类似单调队列的数据结构。

下面是样例 2 的例子帮助理解：

//#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;
typedef double db;
const int MOD=1e9+7;
const int N=2e5+10,M=6e6;
pii a[N];
int p2[M+10];
void INIT()
{p2[0]=1;rep(i,1,M+1) p2[i]=2*p2[i-1]%MOD;
}
int sf_mod(int x,int m=MOD)
{return (x%m+m)%m;
}
bool che(pii a,int x)
{if(a.fi>=30) return true;LL res=(1ll<<a.fi)*a.se;return x<res;
}
inline void Solve()
{int n,x,s=0,m=0;cin>>n;rep(i,0,n){cin>>x;int t=0,val=x;while(!(x&1)) ++t,x/=2;if(m==0||a[m].se>=val){s=(s+val)%MOD;if(t) a[++m]={t,x};}else{a[++m]={t,x};while(m-1&&che(a[m],a[m-1].se)){ // a[m-1].se<(1<<a[m].fi)*a[m].ses=(s-1ll*p2[a[m-1].fi]*a[m-1].se%MOD)%MOD; //s-=(1<<a[m-1].fi)*a[m-1].se;s=sf_mod(s);s=(s+a[m-1].se)%MOD; //s+=a[m-1].se;a[m-1].fi+=a[m].fi;a[m-1].se=a[m].se;m-=1;}s=(s+1ll*p2[a[m].fi]*a[m].se%MOD)%MOD; //s+=(1<<a[m].fi)*a[m].se;if(a[m].fi==0) --m;}cout<<s<<" ";}cout<<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;
}

E. Monster

对于相同次数的增加操作和伤害操作，显然先全部增加后再全部伤害会产生更多的总伤害，本题加上限制 k 次增加，使得伤害达到最大的策略就是：增加 k，伤害 1 次...循环，不妨设这个过程循环了 a 次，最后有 b 次增加，c 次伤害。

于是可以得到最大总伤害为：

$D=k \cdot \frac{a \cdot(a+1)}{2} + (a \cdot k +b) \cdot c$

花费为：

$W=(a \cdot k+b) \cdot x + (a+c) \cdot y$

需要满足 $D \ge z,b \le k$ ，的条件下让 $W$ 尽量小。考虑枚举 a 和 b，注意到 D 的增长是 a 的平方级别，a 枚举量不会超过 $\sqrt{z}$ ，条件可以整理成 $c \ge \left \lceil \frac{z- k\cdot\frac{a \cdot(a+1)}{2}}{a \cdot k +b} \right \rceil$

$c = \left \lceil \frac{z- k\cdot\frac{a \cdot(a+1)}{2}}{a \cdot k +b} \right \rceil \\ =\left \lfloor \frac{z- k\cdot\frac{a \cdot(a+1)}{2}+a \cdot k +b-1}{a \cdot k +b} \right \rfloor\\ = \left \lfloor \frac{z- k\cdot\frac{a \cdot(a+1)}{2}-1}{a \cdot k +b} \right \rfloor +1$

枚举 b 的时候，前面一部分可以使用整除分块技术计算，b 不会超过 k，枚举次数大约在 $\sqrt{k}$ ，最后算出 c 的值。

复杂度： $O(\sum_{a=0}^{\sqrt{\frac{2\cdot z}{k} } } min(\sqrt{z-k\cdot \frac{a\cdot (a+1)}{2} } ,\sqrt{k}))=O(\sqrt{z})$

#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 MEM(a,x) memset(a,x,sizeof(a))
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 N=2e5+10,M=1e9+87;
int x,y,z,k;
LL F(int a,LL b,LL c)
{return (1ll*a*k+b)*x+(a+c)*y;
}
inline void Solve()
{cin>>x>>y>>z>>k;LL ans=1e18;int lim=1e5;rep(a,0,lim+1){LL t=z-1ll*a*(a+1)/2*k;if(t<0) break;LL ak=1ll*a*k;for(LL l=max(ak,1ll),r;l<=t-1;l=r+1){LL b=l-ak;if(b>k) break;r=(t-1)/((t-1)/l);LL c=(t-1)/(ak+b)+1;ans=min(ans,F(a,b,c));}if(t-ak<=k&&t-ak>=0) ans=min(ans,F(a,t-ak,1));}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;
}

F. Tree Operations

考虑 dp，如果进行了 x 次操作，用 f[i] 表示 x 操作之后 i 子树剩余的值，i 节点可以进行的操作次数为 $x/n+[x \mod n \ge i]$ ，这些操作次数用来抵消 $a_{i}$ 以及它的子树剩余的值。

易得递推式： $f[i]=f[j]+a_i-(\frac{x}{n}+[x \mod n \ge i])$ （其中 j 为 i 的子节点）

如果 f[i] 为负数，说明操作数量多了，这时候多出来的操作数只能进行加 1 和减 1，如果次数为偶数刚好为 0。

考虑二分，判断次数是否合法，注意到假如 x 是合法的，则在增加 $2kn$ 次也是合法的（相当于把每个点再增加 k 次又减少 k 次），于是可以把操作次数写成 $2kn+r$ 的形式，枚举 r，再二分出最小 k ，用 dp 判断根节点值是否为 0 即可。

直接写 dfs 的 dp 会被第10个点卡掉，改用拓扑序 dp 才能过。

#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;
typedef double db;
const int MOD=1e9+7;
const int N=2010,M=2*N;
int a[N];
int deg[N],h[N],ne[M],e[M];
LL f[N];
class Graph{
public:int n,r;int idx;vector<int>ts;void add(int a,int b){e[++idx]=b;ne[idx]=h[a];h[a]=idx;}vector<int> Top_sort(){vector<int>res;queue<int>q;rep(i,1,n+1) if(deg[i]==0) q.emplace(i);while(q.size()){int u=q.front(); q.pop();res.emplace_back(u);for(int i=h[u];i;i=ne[i]){int v=e[i];if(--deg[v]==0) q.emplace(v);}}return res;}void Dfs(int u,int fa){for(int i=h[u];i;i=ne[i]){int v=e[i];if(v==fa) continue;Dfs(v,u);}ts.emplace_back(u);}LL Dp(int u,int fa,LL x){ /**TLE**/LL res=a[u]-x/n;if(x%n>=u) res-=1;for(int i=h[u];i;i=ne[i]){int v=e[i];if(v==fa) continue;res+=Dp(v,u,x);}if(res<0) res=(-res)%2;return res;}
}g;
bool che(Graph g,LL x)
{int n=g.n,r=g.r;rep(i,1,n+1) f[i]=0;for(auto u:g.ts){f[u]+=a[u]-x/n;if(x%n>=u) f[u]-=1;if(f[u]<0) f[u]=(-f[u])%2;for(int i=h[u];i;i=ne[i]){int v=e[i];f[v]+=f[u];}}return f[r]==0;
}
inline void Solve()
{g.idx=0;cin>>g.n>>g.r;rep(i,1,g.n+1) cin>>a[i],deg[i]=h[i]=0;rep(i,0,g.n-1){int u,v;cin>>u>>v;g.add(v,u); g.add(u,v);}g.Dfs(g.r,0);LL ans=1e18;rep(i,0,2*g.n){LL l=0,r=1e13;while(l<r){LL mid=l+r>>1;if(che(g,i+mid*2*g.n)) r=mid;else l=mid+1;}if(che(g,i+l*2*g.n)) ans=min(ans,i+l*2*g.n);}cout<<ans<<endl;g.ts.clear();
}
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;
}