title : 第十九届同济大学程序设计竞赛暨高校网络友谊赛
date : 2022-5-30
tags : ACM,题解，练习记录
author : Linno
第十九届同济大学程序设计竞赛暨高校网络友谊赛
题目链接：https://ac.nowcoder.com/acm/contest/34442
A-盒饭盲盒直接打表（感觉大家都推了一段时间）得出式子： ( n − a ) 2 n 2 + a 2 + n a frac{(n-a)^2}{n^2+a^2+na} n2+a2+na(n−a)2
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;
//int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
void Solve(){
int n,a;
cin>>n>>a;
int fz=(n-a)*(n-a),fm=(n*n+a*a+n*a);
int g=gcd(fz,fm);
fz/=g;fm/=g;
cout<
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("in.cpp","r",stdin);
// freopen("out.cpp","w",stdout);
int T=1;
cin>>T;
// clock_t start,finish;
// start=clock();
while(T--){
Solve();
}
// finish=clock();
// cerr<<((double)finish-start)/CLOCKS_PER_SEC<
B-万历十五年
待补
C-攻城
阴间题，要特判一下如果n=1和n=0都是YES，一般情况只要记录所有堡垒需要的伤害数sum,sum%(6+n)==0并且最小值大于sum/(n+6)即可
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;
int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
bool cmp(int x,int y){return x>y;}
int n,h[N],sum,mi;
void Solve(){
n=read();
sum=0;mi=inf;
for(int i=1;i<=n;++i){
h[i]=read();
sum+=h[i];
mi=min(h[i],mi);
}
if(n<=1){puts("YES");}
else if(sum%(6+n)==0){
if(mi>=sum/(n+6)) puts("YES");
else puts("NO");
}else puts("NO");
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("in.cpp","r",stdin);
// freopen("out.cpp","w",stdout);
int T=1;
T=read();
// clock_t start,finish;
// start=clock();
while(T--){
Solve();
}
// finish=clock();
// cerr<<((double)finish-start)/CLOCKS_PER_SEC<
D-两串糖果
dp转移方程
d
p
[
i
]
=
m
a
x
{
d
p
[
j
−
1
]
+
r
e
v
[
j
]
[
i
]
}
dp[i]=max{dp[j-1]+rev[j][i]}
dp[i]=max{dp[j−1]+rev[j][i]}，我们可以用
O
(
n
2
)
O(n^2)
O(n2)获得rev[j][i]表示翻转[j,i]区间后的价值量，求法就是枚举区间长度然后枚举起点。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=5005;
const int mod=1e9+7;
int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
int n,a[N],b[N],c[N],res;
int ans[N][N],rev[N][N],dp[N];
void Solve(){
//cin>>n;
n=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i){
b[i]=read();
rev[i][i]=a[i]*b[i];
}
for(int len=2;len<=n;++len){
for(int i=1;i+len-1<=n;++i){
int j=i+len-1;
rev[i][j]=rev[i+1][j-1]+a[i]*b[j]+a[j]*b[i];
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=i;++j){
dp[i]=max(dp[i],dp[j-1]+rev[j][i]); //翻转后面的区间
}
}
write(dp[n]);
//cout<
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("in.cpp","r",stdin);
// freopen("out.cpp","w",stdout);
int T=1;
// cin>>T;
// clock_t start,finish;
// start=clock();
while(T--){
Solve();
}
// finish=clock();
// cerr<<((double)finish-start)/CLOCKS_PER_SEC<
E-只想要保底
题目形式很容易想到二分答案x，那么我们需要找到矩阵的某两行并起来使得每列都有大于x的那么我们考虑用一个优于
O
(
n
2
)
O(n^2)
O(n2)的方法来做，就可以想到bitset优化，记录前面每行的状态，查看map中是否有与当前行并起来满足条件的行即可。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
#define mk make_pair
#define pii pair
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;
int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
int n,m,a[N][10],p1,p2;
int bi[N],tmp;
mapmp;
pii ans;
inline bool check(int x){
mp.clear();
pii res=mk(inf,inf);
for(int i=1;i<=n;++i){
bi[i]=0;
for(int j=1;j<=m;++j){
bi[i]=(bi[i]<<1)+(a[i][j]>=x);
}
if(!mp.count(bi[i]))mp[bi[i]]=i;
for(int j=0;j<(1<
if((bi[i]|j)==tmp&&mp.count(j)){
p1=i,p2=mp[j];
if(p1>p2) swap(p1,p2);
res=min(res,mk(p1,p2));
}
}
}
if(res.first!=inf){
ans=res;
return true;
}
return false;
}
void Solve(){
n=read();m=read();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
a[i][j]=read();
}
}
for(int i=1;i<=m;++i) tmp=(tmp<<1)+1;
int L=0,R=inf,M;
while(R-L>1){
M=(L+R)/2;
if(check(M)) L=M;
else R=M;
}
write(ans.first);putchar(' ');
write(ans.second);putchar(' ');
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("in.cpp","r",stdin);
// freopen("out.cpp","w",stdout);
int T=1;
// cin>>T;
// clock_t start,finish;
// start=clock();
while(T--){
Solve();
}
// finish=clock();
// cerr<<((double)finish-start)/CLOCKS_PER_SEC<
F-捣乱的神
结论：如果n>=60时，一次合并就可以了。（可以自己动手构造试试）
其他情况下数据范围很小，暴力合并一段区间并且返回这个长度，检查是否满足题意即可。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;
//int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
int n,a[N],s[N],ans=inf;
bool check(int l,int r){
if(l==r) return false;
for(int i=l;i
if((s[i]^s[l-1])>(s[r]^s[i])) return true;
}
return false;
}
void Solve(){
cin>>n;
s[0]=0;
for(int i=1;i<=n;++i){
cin>>a[i];
s[i]=(s[i-1]^a[i]);
}
if(n>=90){ //最多异或一次
cout<<"1n";
return;
}
for(int i=1;i<=n;++i){
for(int j=i;j<=n;++j){
if(check(i,j)){
ans=min(ans,(j-i-1));
}
}
}
if(ans
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("in.cpp","r",stdin);
// freopen("out.cpp","w",stdout);
int T=1;
// cin>>T;
// clock_t start,finish;
// start=clock();
while(T--){
Solve();
}
// finish=clock();
// cerr<<((double)finish-start)/CLOCKS_PER_SEC<
G-归零
对于小于等于k/2的数，考虑将其变为0，对于大于k/2的数，考虑将其变为k，那么这个过程就要求区间的数可以有序，很容易想到用主席树做。我们得到表示[l,r]的权值线段树后，按k/2划分两部分进行求和即可得到答案。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 1e9
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;
//int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
struct Q{int l,r,k;}q[N];
struct node{
int ls,rs,cnt,sum;
}tr[N<<5];
int idx=0;
int n,m,len,a[N],rt[N];
inline void update(int &p,int o,int l,int r,int val){
p=++idx;
tr[p]=tr[o];
++tr[p].cnt;
tr[p].sum+=val;
if(l==r) return;
int mid=((l+r)>>1);
if(val<=mid) update(tr[p].ls,tr[o].ls,l,mid,val);
else update(tr[p].rs,tr[o].rs,mid+1,r,val);
}
int S,T;
inline int query1(int p,int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return tr[p].sum-tr[o].sum;
int mid=((l+r)>>1);
int res=0;
if(ql<=mid) res+=query1(tr[p].ls,tr[o].ls,l,mid,ql,qr);
if(qr>mid) res+=query1(tr[p].rs,tr[o].rs,mid+1,r,ql,qr);
return res;
}
inline int query2(int p,int o,int l,int r,int ql,int qr,int k){
if(ql<=l&&r<=qr) return (tr[p].cnt-tr[o].cnt)*k-(tr[p].sum-tr[o].sum);
int mid=((l+r)>>1);
int res=0;
if(ql<=mid) res+=query2(tr[p].ls,tr[o].ls,l,mid,ql,qr,k);
if(qr>mid) res+=query2(tr[p].rs,tr[o].rs,mid+1,r,ql,qr,k);
return res;
}
void Solve(){
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=1;i<=m;++i){
cin>>q[i].l>>q[i].r>>q[i].k;
}
for(int i=1;i<=n;++i){
update(rt[i],rt[i-1],0,inf,a[i]);
}
for(int i=1;i<=m;++i){
int ans=0;
ans+=query1(rt[q[i].r],rt[q[i].l-1],0,inf,0,q[i].k/2);
ans+=query2(rt[q[i].r],rt[q[i].l-1],0,inf,q[i].k/2+1,inf,q[i].k);
cout<
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("in.cpp","r",stdin);
// freopen("out.cpp","w",stdout);
int T=1;
// cin>>T;
// clock_t start,finish;
// start=clock();
while(T--){
Solve();
}
// finish=clock();
// cerr<<((double)finish-start)/CLOCKS_PER_SEC<
H-打工人
比较裸的单调队列优化，状态转移方程
d
p
[
i
]
=
d
p
[
j
]
+
s
[
j
−
>
i
]
+
2
dp[i]=dp[j]+s[j->i]+2
dp[i]=dp[j]+s[j−>i]+2
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
#define pii pair
#define mk make_pair
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;
//int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
int n,K,W,p[N],w[N],s[N],dp[N];
pii q[N];
void Solve(){
cin>>n>>K>>W;
for(int i=1;i<=n;++i){
cin>>p[i]>>w[i];
s[i]=s[i-1];
if(p[i]!=p[i-1]) ++s[i];
w[i]+=w[i-1]; //前缀和
}
int head=0,tail=-1;
q[++tail]={0,-1};
for(int i=1;i<=n;++i){
while(head<=tail&&(i-q[head].first>K||w[i]-w[q[head].first]>W)) ++head;
dp[i]=q[head].second+s[i]+2;
pii fro={i,dp[i]-s[i+1]};
while(head<=tail&&(q[tail].second>=fro.second)) --tail;
q[++tail]=fro;
}
cout<
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("in.cpp","r",stdin);
// freopen("out.cpp","w",stdout);
int T=1;
// cin>>T;
// clock_t start,finish;
// start=clock();
while(T--){
Solve();
}
// finish=clock();
// cerr<<((double)finish-start)/CLOCKS_PER_SEC<
I-另类排序
不会，有空再补。
J-收集者
考虑以一个某个位置的0/1结尾对答案的贡献。1可以作为开头所以另外+1，有单个令的情况对整体贡献为1，对每个位置的答案都可以由前面0、1答案的前缀和进行转移。
d
p
[
0
]
=
d
p
[
0
]
+
d
p
[
1
]
d
p
[
1
]
=
d
p
[
0
]
+
d
p
[
1
]
+
1
dp[0]=dp[0]+dp[1]\ dp[1]=dp[0]+dp[1]+1
dp[0]=dp[0]+dp[1]dp[1]=dp[0]+dp[1]+1
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;
//int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
string str;
int tmp,dp[2];
void Solve(){
cin>>str;
int n=str.length();
for(int i=0;i
if(str[i]=='0'){
tmp=1; //只有一个0的情况
dp[0]=(dp[0]+dp[1])%mod;
}else dp[1]=(dp[1]+dp[0]+1)%mod;
}
cout<<(dp[0]+dp[1]+tmp)%mod;
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("in.cpp","r",stdin);
// freopen("out.cpp","w",stdout);
int T=1;
// cin>>T;
// clock_t start,finish;
// start=clock();
while(T--){
Solve();
}
// finish=clock();
// cerr<<((double)finish-start)/CLOCKS_PER_SEC<
K-乐观的R家族
签到题，统计然后输出答案即可。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;
//int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
string str[N];
int n,m,a[N],cnt[10],ans=0;
void Solve(){
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>str[i];
}
for(int i=1;i<=m;++i) cin>>a[i];
for(int i=1;i<=m;++i){
memset(cnt,0,sizeof(cnt));
int mx=0;
for(int j=1;j<=n;++j){
++cnt[str[j][i-1]-'A'];
}
for(int j=0;j<5;++j) if(cnt[j]>cnt[mx]) mx=j;
ans+=cnt[mx]*a[i];
// cout<
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("in.cpp","r",stdin);
// freopen("out.cpp","w",stdout);
int T=1;
// cin>>T;
// clock_t start,finish;
// start=clock();
while(T--){
Solve();
}
// finish=clock();
// cerr<<((double)finish-start)/CLOCKS_PER_SEC< 
