H.Beacon Towers
发现分界点为使得前缀最大值变化的点。
根据乘法原理，可知答案即为相邻分界点之间距离乘积。
即，假设分界点为 $p_1,p_2,\dots ,p_m$ ，答案即为 $\prod\limits_{i=1}^{m-1}(p_{i+1}-p_i+1)$
代码
#include<bits/stdc++.h>
#define ll long long
#define N 500010
#define mod 1000000007
using namespace std;
int n,h[N];
void solve() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
int maxn=h[1],maxid=1;
ll ans=1;
for(int i=2;i<=n;i++) {
if(h[i]>maxn) {
(ans*=i-maxid+1)%=mod;
maxn=h[i];
maxid=i;
}
}
printf("%lld\n",ans);
}
int main() {
solve();
return 0;
}A.Factory Balls
发现 $n,k,m$ 值都很小。
状压 + BFS 。
设 $f[x][y]$ 表示染色符合的状态为 $x$ ，装置使用的状态为 $y$ 时的最小步数。
直接 BFS 即可。
时间复杂度 $O\big(2^{n+m}(kn+m)\big)$ 。
代码
#include<bits/stdc++.h>
#define N 11
#define INF 0x3f3f3f3f
using namespace std;
int n,k,m,c[N],eqp[N][N],f[1<<N][1<<N],st=0;
bool vh[N];
queue<pair<int,int> > q;
void bfs() {
memset(f,0x3f,sizeof(f));
q.push(make_pair(st,0));
f[st][0]=0;
while(!q.empty()) {
pair<int,int> u=q.front();q.pop();
int X=u.first,Y=u.second;
//cout<<"test"<<X<<" "<<Y<<" "<<f[X][Y]<<endl;
//system("pause");
for(int i=0;i<m;i++) {
int nY=Y^(1<<i);
if(f[X][nY]>f[X][Y]+1) {
f[X][nY]=f[X][Y]+1;
q.push(make_pair(X,nY));
}
}
for(int i=0;i<n;i++) vh[i]=false;
for(int i=0;i<m;i++) if(Y&(1<<i)) for(int j=1;j<=eqp[i][0];j++) vh[eqp[i][j]]=true;
//for(int i=0;i<n;i++) cout<<vh[i]<<" ";
//cout<<endl;
for(int i=0;i<k;i++) {
int nX=X;
for(int j=0;j<n;j++) {
if(!vh[j]) {
if(i==c[j]) nX|=(1<<j);
else nX=nX&(((1<<n)-1)^(1<<j));
}
}
if(f[nX][Y]>f[X][Y]+1) {
f[nX][Y]=f[X][Y]+1;
q.push(make_pair(nX,Y));
}
}
}
}
void solve() {
scanf("%d%d%d",&n,&k,&m);
for(int i=0;i<n;i++) {
scanf("%d",&c[i]);
c[i]--;
if(!c[i]) st|=(1<<i);
}
for(int i=0;i<m;i++) {
scanf("%d",&eqp[i][0]);
for(int j=1;j<=eqp[i][0];j++) {
scanf("%d",&eqp[i][j]);
eqp[i][j]--;
}
}
bfs();
if(f[(1<<n)-1][0]==INF) printf("-1\n");
else printf("%d\n",f[(1<<n)-1][0]);
}
int main() {
solve();
system("pause");
return 0;
}F.Stones 1
把同色的缩成一个点，值取其中最大的。
然后就得到了一个黑白相间的序列，假设长度为 $m$ 。
动手模拟，发现取中间的前 $\lceil \frac{m-2}{2}\rceil$ 大的即可。
因为最多能取 $\lceil \frac{m-2}{2}\rceil$ 个，然后肯定往大的取，发现总有方案可以取到这些大的。
学长的解释：
代码
#include<bits/stdc++.h>
#define ll long long
#define N 300010
using namespace std;
int n,tot=0;
ll a[N],A[N],ans=0;
char s[N];
vector<ll> val;
void solve() {
scanf("%d",&n);
scanf("%s",s+1);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
int m=0;
for(int i=1;i<=n;i++) {
ll maxn=a[i];
while(s[i]==s[i+1]) {
i++;
maxn=max(maxn,a[i]);
}
A[++tot]=maxn;
}
if(tot<=2) printf("0\n");
else {
for(int i=2;i<tot;i++) val.push_back(A[i]);
sort(val.begin(),val.end());
int num=(tot&1)?(tot-1)/2:(tot-2)/2,sz=val.size();
for(int i=sz-1;i>=sz-num;i--) ans+=val[i];
printf("%lld\n",ans);
}
}
int main() {
solve();
return 0;
}D.Triple Sword Strike
三刀，有两种情况。
一种三刀平行，另一种两刀平行，一刀垂直。
贴学长写的题解。
补题的时候没有看到坐标可以取 $0$ ，导致 RE 了好多发。
一定一定一定要注意数据范围。
代码
#include<bits/stdc++.h>
#define N 1000010
using namespace std;
const int M=1000000;
int n,x[N],y[N],v[N],R[N],C[N];
vector<pair<int,int> > RC[N],CR[N];
multiset<int,greater<> > RR,CC;
void solve() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&y[i],&v[i]);
for(int i=1;i<=n;i++) {
R[x[i]]+=v[i];
C[y[i]]+=v[i];
RC[x[i]].push_back(make_pair(y[i],i));
CR[y[i]].push_back(make_pair(x[i],i));
}
for(int i=0;i<=M;i++) if(R[i]) RR.insert(R[i]);
for(int i=0;i<=M;i++) if(C[i]) CC.insert(C[i]);
int ans=0,sumR=0,sumC=0,cntR=0,cntC=0;
for(multiset<int>::iterator p=RR.begin();p!=RR.end();p++) {
cntR++;
sumR+=*p;
if(cntR==3) break;
}
for(multiset<int>::iterator p=CC.begin();p!=CC.end();p++) {
cntC++;
sumC+=*p;
if(cntC==3) break;
}
ans=max(sumR,sumC);
for(int i=0;i<=M;i++) {
int sz=RC[i].size();
if(!sz) continue;
for(int j=0;j<sz;j++) {
CC.erase(CC.find(C[RC[i][j].first]));
C[RC[i][j].first]-=v[RC[i][j].second];
CC.insert(C[RC[i][j].first]);
}
int cnt=0,sum=0;
for(multiset<int>::iterator p=CC.begin();p!=CC.end();p++) {
cnt++;
sum+=*p;
if(cnt==2) break;
}
ans=max(ans,sum+R[i]);
for(int j=0;j<sz;j++) {
CC.erase(CC.find(C[RC[i][j].first]));
C[RC[i][j].first]+=v[RC[i][j].second];
CC.insert(C[RC[i][j].first]);
}
}
for(int i=0;i<=M;i++) {
int sz=CR[i].size();
if(!sz) continue;
for(int j=0;j<sz;j++) {
RR.erase(RR.find(R[CR[i][j].first]));
R[CR[i][j].first]-=v[CR[i][j].second];
RR.insert(R[CR[i][j].first]);
}
int cnt=0,sum=0;
for(multiset<int>::iterator p=RR.begin();p!=RR.end();p++) {
cnt++;
sum+=*p;
if(cnt==2) break;
}
ans=max(ans,sum+C[i]);
for(int j=0;j<sz;j++) {
RR.erase(RR.find(R[CR[i][j].first]));
R[CR[i][j].first]+=v[CR[i][j].second];
RR.insert(R[CR[i][j].first]);
}
}
printf("%d\n",ans);
}
int main() {
solve();
system("pause");
return 0;
}E. RPS Bubble Sort
思维题。
直接贴题解。
真的 好妙。
代码
#include<bits/stdc++.h>
#define N 500010
using namespace std;
int n,t;
char s[N];
map<char,int> cnt;
bool vh[N];
void solve(int l,int r) {
char winner,loser;
if(!cnt['R']) winner='S',loser='P';
else if(!cnt['S']) winner='P',loser='R';
else winner='R',loser='S';
int rk=l;
for(int i=l;i<=r;i++) if(s[i]==loser) vh[max(rk,i-t)]=true,rk++;
for(int i=l;i<=r;i++) {
if(vh[i]) printf("%c",loser);
else printf("%c",winner);
}
cnt[winner]=cnt[loser]=0;
}
void work() {
scanf("%d%d",&n,&t);
scanf("%s",s+1);
int l=1;
for(int i=1;i<=n;i++) {
cnt[s[i]]++;
if(cnt['R']&&cnt['S']&&cnt['P']) {
cnt[s[i]]--;
solve(l,i-1);
l=i;
cnt[s[i]]++;
}
}
solve(l,n);
printf("\n");
}
int main() {
work();
return 0;
}
