Problem
T1
累加燃烧度,除以 \(m\) 即为答案。
需要开 unsigned __int128
,差评。
T2
若有 \(a,b\) 满足 \(a-c=c-b\),化简此式可得 \(a+b=2c\),说明 \(a+b\) 必须为偶数。
于是我们倒序求一遍后缀偶数个数 \(os_i\) 和奇数个数 \(js_i\);
然后枚举每一个 \(i\),若它是奇数,则它可以和它后面的 \(js_i-1\) 个奇数配对,否则可以和它后面的 \(os_i-1\) 个偶数配对。依次累加贡献即可。
T3
用队列维护口味值,令 \(cnt\) 为队列中的不同口味值数量,\(t_i\) 为口味值为 \(i\) 的数量。
先将口味值依次入队,直到其中有 \(m\) 种不同的口味,并且在入队的过程中更新 \(t_i\)。
然后不断弹出队首(即第 \(m\) 种口味),直到第 \(m\) 种口味消失,此时更新 \(ans\) 为 \(\max(ans,top-i+1)\)(\(i\) 是弹出前的队首,\(top\) 是当前队首)。
重复上述操作 \(n\) 次即可得到答案。
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=1e9,a[100031];
int cnt,top,t[100031];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
while(cnt!=m){
top++;
if(top>n) break;
if(!t[a[top]]) cnt++;
t[a[top]]++;
}
ans=min(ans,top);
for(int i=1;i<=n&&top<=n;i++){
t[a[i]]--;
if(t[a[i]]) continue;
ans=min(ans,top-i+1);
cnt--;
while(cnt!=m){
top++;
if(top>n) break;
if(!t[a[top]]) cnt++;
t[a[top]]++;
}
}
cout<<ans;
return 0;
}
T4
简单 bfs。
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int n,ans=1e9,xa,ya,xb,yb;
char mp[1031][1031];
int dis[2][1031][1031];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void upd(int x,int y,int nx,int ny,queue<pii> &q,int d[1031][1031]){
if(d[nx][ny]==-1&&mp[nx][ny]=='0'){
d[nx][ny]=d[x][y]+1;
q.push(make_pair(nx,ny));
}
}
void bfs_z(int sx,int sy){
queue<pii> q;
memset(dis[0],-1,sizeof(dis[0]));
for(upd(0,0,sx,sy,q,dis[0]);!q.empty();q.pop()){
int x=q.front().first,y=q.front().second;
for(int i=0;i<4;i++){
upd(x,y,x+dx[i],y+dy[i],q,dis[0]);
if(mp[x+dx[i]][y+dy[i]]=='0')
for(int j=0;j<4;j++) upd(x,y,x+dx[i]+dx[j],y+dy[i]+dy[j],q,dis[0]);
}
}
}
void bfs_m(int sx,int sy){
queue<pii> q;
memset(dis[1],-1,sizeof(dis[1]));
for(upd(0,0,sx,sy,q,dis[1]);!q.empty();q.pop()){
int x=q.front().first,y=q.front().second;
for(int i=0;i<4;i++){
upd(x,y,x+dx[i],y+dy[i],q,dis[1]);
if(mp[x+dx[i]][y+dy[i]]=='1') upd(x,y,x+2*dx[i],y+2*dy[i],q,dis[1]);
}
}
}
int main(){
cin>>n>>xa>>ya>>xb>>yb;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>mp[i][j];
bfs_z(xa,ya),bfs_m(xb,yb);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(mp[i][j]=='0'&&dis[0][i][j]!=-1&&dis[1][i][j]!=-1)
ans=min(ans,max(dis[0][i][j],dis[1][i][j]));
cout<<ans;
return 0;
}
标签:总结,YL,int,top,ny,ans,1031,模拟,dis
From: https://www.cnblogs.com/XOF-0-0/p/18049280