A
判断有没有两维均大于等于第一个人的人即可。有就无解，否则答案为 \(s_1\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
int n,stx,sty;
void solve(){
read(n);
read(stx),read(sty);
bool flag=1;
for(int i=2,x,y;i<=n;i++){
read(x),read(y);
if(x>=stx&&y>=sty){
flag=0;
}
}
if(flag){
write_endl(stx);
}
else{
write_endl(-1);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
B
容易发现，选择的一定是一行或一列，求所有行与列中答案最小的即可。
注意要开 long long。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3e5+10;
int n,sum1,sum2,a[N],b[N],mn1,mn2;
void solve(){
sum1=sum2=0;
mn1=mn2=inf;
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
sum1+=a[i];
mn1=min(mn1,a[i]);
}
for(int i=1;i<=n;i++){
read(b[i]);
sum2+=b[i];
mn2=min(mn2,b[i]);
}
write_endl(min(mn1*n+sum2,mn2*n+sum1));
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
C
推错式子，吃了两发罚时，好烦。
先算数量，将连续的相同的数缩成一块，假定第 \(i\) 块的大小为 \(s_i\)，答案 \(num=\sum s_i\)。
再算方案，因为每个连续段是分开的并不会相互影响，先删A块中的数再删B块中的数和反过来是两种方案，所以删除的数是可以任意排列。选出删除的数的方案为 \(\prod s_i\)，排列的方案为 \(num!\)，总方案数为 \(\prod s_i\times num!\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10,mod=998244353;
string s;
int fac[N],inv[N];
int qpow(int a,int b){
int res=1;
while(b){
if(b&1){
res=res*a%mod;
}
a=a*a%mod;
b>>=1;
}
return res;
}
void init(int mx){
fac[0]=1;
for(int i=1;i<=mx;i++){
fac[i]=fac[i-1]*i%mod;
}
inv[mx]=qpow(fac[mx],mod-2);
for(int i=mx-1;i>=0;i--){
inv[i]=inv[i+1]*(i+1)%mod;
}
}
void solve(){
cin>>s;
int num=1;
vector<int>sum;
for(int i=1;i<s.size();i++){
if(s[i]!=s[i-1]){
sum.pb(num);
num=1;
}
else{
num++;
}
}
sum.pb(num);
sort(sum.begin(),sum.end());
int ans=1,res=0;
for(auto x:sum){
res+=x-1;
ans*=x;
ans%=mod;
}
write_space(res),write_endl(ans*fac[res]%mod);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
init(2e5);
int t;
read(t);
while(t--){
solve();
}
return 0;
}
D
先做前缀和，令 \(s_i\) 表示 \(\oplus_{j=1}^i a_j\)，可得 \(ans=\sum\limits_{i=0}^n\sum\limits_{j=0}^{i-1}(s_i\oplus s_j)\times(i-j)\)
拆开 \(ans=\sum\limits_{i=0}^n\sum\limits_{j=0}^{i-1}(s_i\oplus s_j)\times i-\sum\limits_{j=0}^n\sum\limits_{i=j+1}^{n}(s_i\oplus s_j)\times j\)。
可以发现两个部分是等价的。算出前一个部分的贡献，再反过来做一遍求出后一个部分的贡献并将其减掉即可。拆到每一位，令 \(cnt_i\) 表示第 \(i\) 位有值的数的个数。对于 \(s_j\) 有值的位 \(i\)，贡献为 \((j-cnt_i)\times j\times 2^i\)，否则贡献为 \(cnt_i\times j\times 2^i\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3e5+10,Lg=30,mod=998244353;
int n,a[N],s[N],cnt[Lg+5];
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
s[i]=s[i-1]^a[i];
}
int ans=0;
for(int i=0;i<=n;i++){
for(int j=0;j<=Lg;j++){
if(s[i]>>j&1){
ans=(ans+i*(i-cnt[j])%mod*(1<<j)%mod)%mod;
cnt[j]++;
continue;
}
ans=(ans+i*cnt[j]%mod*(1<<j)%mod)%mod;
}
}
// cerr<<ans<<endl;
for(int i=0;i<=Lg;i++){
cnt[i]=0;
}
for(int i=n;i>=0;i--){
for(int j=0;j<=Lg;j++){
if(s[i]>>j&1){
ans=(ans+mod-i*((n-i)-cnt[j])%mod*(1<<j)%mod)%mod;
cnt[j]++;
continue;
}
ans=(ans+mod-i*cnt[j]%mod*(1<<j)%mod)%mod;
}
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
E
被题意恶心到了，导致没有做出来本题。
简明题意：用尽量少的颜色将一棵树的边染色，并得到一个策略，使得无论给出与哪个点相连的边的染色情况，都根据策略选出一个颜色，且该颜色只有一条往根走的边。
给出结论，颜色数一定小于等于 \(3\)。因为不会其它证明，所以只给出构造性证明，即提供构造方法。
颜色数为 \(1\)：该图为菊花图。
颜色数为 \(2\)：所有 \(deg\) 等于 \(2\) 的点的深度模 \(2\) 的余数相同。颜色为 \(2\) 肯定是交替出现，对于度数为 \(2\) 的点肯定是要给出一个统一策略的，即所有度数为 \(2\) 的点的染色情况是一定的。
颜色数为 \(3\)：将深度模 \(3\) 的值视作到父亲的边的颜色，这时 \(deg\) 为 \(2\) 的点会划分为三种，\(cnt_1=cnt_2=1\)；\(cnt_2=cnt_3=1\)；\(cnt_1=cnt_3=1\)。对于这三种情况，每个情况都可以有唯一的方案去选择颜色，剩下的点直接找数量为 \(1\) 的颜色即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,fa[N],dep[N],sum=-1,ans[N];
vector<int>e[N];
bool flag=1;
void dfs(int u){
if(e[u].size()==1){
cerr<<u<<' '<<dep[u]<<endl;
if(sum==-1){
sum=(dep[u]-1)&1;
}
if(sum!=((dep[u]-1)&1)){
flag=0;
}
}
for(auto v:e[u]){
dfs(v);
}
}
void query(int u){
for(auto v:e[u]){
query(v);
}
if(sum<=0){
ans[u]=((dep[u]-1)&1)+1;
}
else{
ans[u]=(dep[u]&1)+1;
}
}
signed main(){
cin>>n;
for(int i=2;i<=n;i++){
cin>>fa[i];
dep[i]=dep[fa[i]]+1;
e[fa[i]].push_back(i);
if(dep[i]>1){
flag=0;
}
}
if(flag){
cout<<1<<endl;
for(int i=2;i<=n;i++){
cout<<1<<' ';
}
cout<<endl;
int x;
cin>>x>>x;
cout<<1<<endl;
return 0;
}
flag=1;
for(auto v:e[1]){
sum=-1;
dfs(v);
query(v);
}
if(flag){
cout<<2<<endl;
for(int i=2;i<=n;i++){
cout<<ans[i]<<' ';
}
cout<<endl;
while(1){
int a,b,opt;
cin>>opt;
if(opt==1||opt==-1){
break;
}
cin>>a>>b;
if(a==1){
cout<<1<<endl;
}
else{
cout<<2<<endl;
}
}
return 0;
}
cout<<3<<endl;
for(int i=2;i<=n;i++){
cout<<dep[i]%3+1<<' ';
}
cout<<endl;
while(1){
int opt,a,b,c;
cin>>opt;
if(opt==1||opt==-1){
break;
}
cin>>a>>b>>c;
if(c!=0&&b==1){
cout<<2<<endl;
}
else if(a!=0&&c==1){
cout<<3<<endl;
}
else if(b!=0&&a==1){
cout<<1<<endl;
}
else if(a==1){
cout<<1<<endl;
}
else if(b==1){
cout<<2<<endl;
}
else if(c==1){
cout<<3<<endl;
}
}
return 0;
}
F
题意：对于一个 \(t\)，令 \(b_i=\lceil\frac{a_i}{t}\rceil\times h_i\)，对于每个位置 \(i\)，其 \(b_i\) 为最大值时，\(b_i-b_{cmax}\) 的差的最大值，其中 \(cmax\) 表示次大值的位置。
枚举 \(t\in [0,\max a_i]\)，枚举 \(\lceil\frac{a_i}{t}\rceil\)，对应的权值是一段区间。因为只要求最大值和次大值，可以用 ST 表维护区间的权值对应的 \(h_i\) 最大值和次大值及对应位置。可以在 \(O(n\log n)\) 的复杂度求出最大值与次大值的值。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10,Lg=20;
int n,lg[N],h[N],a[N];
struct node{
pii mx,nxt;
}ST[N][Lg+5];
node merge(node x,node y){
node z=node{max(x.mx,y.mx),max(x.nxt,y.nxt)};
if(x.mx!=y.mx){
z.nxt=max(z.nxt,min(x.mx,y.mx));
}
return z;
}
node query(int l,int r){
return merge(ST[l][lg[r-l+1]],ST[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
int ans[N];
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(h[i]);
}
int mx=0;
for(int i=1;i<=n;i++){
read(a[i]);
mx=max(mx,a[i]);
--a[i];
ans[i]=0;
}
if(n==1){
write_endl((a[1]+1)*h[1]);
return;
}
for(int i=0;i<=mx;i++){
ST[i][0]=node{mp(0,0),mp(0,0)};
}
for(int i=1;i<=n;i++){
ST[a[i]][0]=merge(ST[a[i]][0],node{mp(h[i],i),mp(0,0)});
}
for(int i=1;i<=Lg;i++){
for(int j=0;j+(1<<i)-1<=mx;j++){
ST[j][i]=merge(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
}
}
for(int i=1;i<=mx;i++){
node res=node{mp(0,0),mp(0,0)};
for(int j=1;(j-1)*i<=mx;j++){
int l=(j-1)*i,r=j*i-1;
r=min(r,mx);
node x=query(l,r);
x.mx.first*=j;
x.nxt.first*=j;
res=merge(res,x);
}
ans[res.mx.second]=max(ans[res.mx.second],res.mx.first-res.nxt.first);
}
for(int i=1;i<=n;i++){
write_space(ans[i]);
}
putchar('\n');
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
lg[0]=-1;
for(int i=1;i<N;i++){
lg[i]=lg[i>>1]+1;
}
int t;
read(t);
while(t--){
solve();
}
return 0;
}