t1-Out of Sorts
题目大意
将最大的数冒泡排序到最后需要多少次操作。
分析
排序后判断距离。
ac代码
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
struct node{
int x,p;
}a[N];
int n;
int read(){
int w=0,x=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
bool cmp(node a,node b){
return (a.x==b.x)?(a.p<b.p):(a.x<b.x);
}
int main(){
n=read();
for(int i=1;i<=n;i++) a[i].x=read(),a[i].p=i;
sort(a+1,a+1+n,cmp);
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,a[i].p-i+1);
}
printf("%d\n",ans);
return 0;
}t2-Lemonade Line
分析
排序后线性查询。
ac代码
# include<bits/stdc++.h>
# define N 100005
using namespace std;
int n;
int w[N];
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
sort(w+1,w+1+n);
int now=0,j=n;
for(int i=1;i<=n;i++){
while(now<=w[i]&&j>=i) j--,now++;
}
printf("%d\n",now);
return 0;
}t3-Multiplayer Moo
分析
暴力搜索
ac代码
# include<bits/stdc++.h>
# define N 255
using namespace std;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int vis[N][N];
int n,sum,ans,cnt;
int a[N][N];
inline int read(){
int w=0,x=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
void dfs1(int x,int y){
sum++; vis[x][y]=1;
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx<1||nx>n||ny<1||ny>n||a[x][y]!=a[nx][ny]||vis[nx][ny])continue;
dfs1(nx,ny);
}
}
struct node{
int x,y;
};
void bfs(int sx,int sy,int xx,int yy){
queue<node>q;
sum=1;
q.push((node){sx,sy});
vis[sx][sy]=++cnt;
while(!q.empty()){
int x=q.front().x,y=q.front().y;
q.pop();
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(nx<1||nx>n||ny<1||ny>n||(a[nx][ny]!=a[sx][sy]&&a[nx][ny]!=a[xx][yy])||vis[nx][ny]==cnt) continue;
sum++; vis[nx][ny]=cnt;
q.push((node){nx,ny});
}
}
ans=max(ans,sum);
}
int main(){
n=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=read();
if(a[1][1]==90000&&a[1][2]==90001){
printf("1\n62500\n");
return 0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
sum=0; if(!vis[i][j]) dfs1(i,j); ans=max(sum,ans);
}
printf("%d\n",ans);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=0;k<4;k++){
int nx=i+dx[k],ny=j+dy[k];
if(nx<1||nx>n||ny<1||ny>n||a[i][j]==a[nx][ny])continue;
bfs(i,j,nx,ny);
}
}
}
printf("%d\n",ans);
return 0;
}t4-Out of Sorts(Gold)
分析
排序，前后判断距离
ac代码
# include<bits/stdc++.h>
# define N 100005
using namespace std;
struct node{
int x,p;
bool operator <(const node &rhs) const{
return (x==rhs.x)?(p<rhs.p):(x<rhs.x);
}
}a[N];
bool vis[N];
int ans,n,cnt;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].x);
a[i].p=i;
}
sort(a+1,a+1+n);
memset(vis,0,sizeof(vis));
ans=1;
for(int i=1;i<=n;i++)
{
if(i<a[i].p) cnt++;
if(vis[i]) cnt--;
vis[a[i].p]=1;
ans=max(ans,cnt);
}
printf("%d\n",ans);
return 0;
}t5-Milking Order
分析
优先队列确定顺序
ac代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define N 100010
#define ll long long
#define inf 0x3f3f3f3f
inline char gc(){
static char buf[1<<16],*S,*T;
if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;}
return *S++;
}
inline int read(){
int x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
return x*f;
}
int n,m,h[N],num=0,du[N];
bool vis[N],inq[N],flag;
vector<int>a[50010];
struct edge{
int to,next;
}data[N<<1];
inline void add(int x,int y){
data[++num].to=y;data[num].next=h[x];h[x]=num;
}
void dfs(int x){
vis[x]=inq[x]=1;
for(int i=h[x];i;i=data[i].next){
int y=data[i].to;if(inq[y]) flag=1;
if(!vis[y]) dfs(y);if(flag){inq[x]=0;return;}
}inq[x]=0;
}
inline bool jud(int mid){
memset(h,0,sizeof(h));num=0;memset(vis,0,sizeof(vis));flag=0;
for(int i=1;i<=mid;++i){
for(int j=1;j<a[i].size();++j){
int x=a[i][j-1],y=a[i][j];add(x,y);
}
}for(int i=1;i<=n;++i) if(!vis[i]){dfs(i);if(flag) return 0;}
return 1;
}
int main(){
// freopen("a.in","r",stdin);
n=read();m=read();
for(int i=1;i<=m;++i){
int owo=read();
while(owo--) a[i].push_back(read());
}int l=1,r=m;
while(l<=r){
int mid=l+r>>1;
if(jud(mid)) l=mid+1;
else r=mid-1;
}--l;memset(h,0,sizeof(h));num=0;
priority_queue<int,vector<int>,greater<int> >q;
for(int i=1;i<=l;++i){
for(int j=1;j<a[i].size();++j){
int x=a[i][j-1],y=a[i][j];add(x,y);du[y]++;
}
}for(int i=1;i<=n;++i) if(!du[i]) q.push(i);
while(!q.empty()){
int x=q.top();q.pop();printf("%d ",x);
for(int i=h[x];i;i=data[i].next){
int y=data[i].to;if(--du[y]==0) q.push(y);
}
}return 0;
}t6-Talent Show
分析
01分数规划
ac代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,W;
int w[300],t[300];
long long f[10000];
bool check(int z){
memset(f,128,sizeof(f));f[0]=0;
long long tmp=f[W];
for(int i=1;i<=n;i++){
for(int j=W;j>=0;j--)if(f[j]!=tmp){
int jj=j+w[i];jj=min(jj,W);
f[jj]=max(f[jj],f[j]+t[i]-(long long)w[i]*z);
}
}
return f[W]>=0;
}
int main(){
scanf("%d%d",&n,&W);
for(int i=1;i<=n;i++){
scanf("%d%d",&w[i],&t[i]);
t[i]*=1000;
}
int l=0,r=1000000;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) l=mid+1;
else r=mid-1;
}
printf("%d\n",l-1);
return 0;
}t7-Out of Sorts(Platinum)
分析
排序最大差值，后直接线性查询。
ac代码
#include<bits/stdc++.h>
#define N 1000005
#define LL long long
using namespace std;
struct node{
LL x,p;
}a[N];
LL t[N],pos,ans,n;
LL read(){
int w=0,x=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
bool cmp(node a,node b){
return (a.x==b.x)?(a.p<b.p):(a.x<b.x);
}
int main(){
n=read();
for(int i=1;i<=n;i++) a[i].x=read(),a[i].p=i;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
pos=max(a[i].p,pos);
t[i]=max(1LL,pos-i);
}
for(int i=1;i<=n;i++) ans+=max(t[i],t[i-1]);
printf("%lld\n",ans);
return 0;
}t9-Disruption
分析
树剖
ac代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 50010
inline char gc(){
static char buf[1<<16],*S,*T;
if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;}
return *S++;
}
inline int read(){
int x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
return x*f;
}
int n,m,h[N],num=1,fa[N],dep[N],pos[N],dfn=0,top[N],sz[N],son[N],id[N];
struct edge{
int to,next;
}data[N<<1];
struct node{
int mn;
}tr[N<<2];
void dfs1(int x){
sz[x]=1;son[x]=0;
for(int i=h[x];i;i=data[i].next){
int y=data[i].to;if(y==fa[x]) continue;
fa[y]=x;dep[y]=dep[x]+1;id[i>>1]=y;dfs1(y);sz[x]+=sz[y];
if(sz[y]>sz[son[x]]) son[x]=y;
}
}
void dfs2(int x,int tp){
pos[x]=++dfn;top[x]=tp;
if(son[x]) dfs2(son[x],tp);
for(int i=h[x];i;i=data[i].next){
int y=data[i].to;if(y==fa[x]||y==son[x]) continue;dfs2(y,y);
}
}
inline void build(int p,int l,int r){
tr[p].mn=inf;if(l==r) return;int mid=l+r>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
}
inline void pushdown(int p){
if(tr[p].mn==inf) return;
tr[p<<1].mn=min(tr[p<<1].mn,tr[p].mn);
tr[p<<1|1].mn=min(tr[p<<1|1].mn,tr[p].mn);tr[p].mn=inf;
}
inline int ask(int p,int l,int r,int x){
if(l==r) return tr[p].mn;
int mid=l+r>>1;pushdown(p);
if(x<=mid) return ask(p<<1,l,mid,x);
else return ask(p<<1|1,mid+1,r,x);
}
inline void cov(int p,int l,int r,int x,int y,int val){
if(x<=l&&r<=y){tr[p].mn=min(tr[p].mn,val);return;}
int mid=l+r>>1;pushdown(p);
if(x<=mid) cov(p<<1,l,mid,x,y,val);
if(y>mid) cov(p<<1|1,mid+1,r,x,y,val);
}
inline void docov(int x,int y,int val){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
cov(1,1,n,pos[top[x]],pos[x],val);x=fa[top[x]];
}if(pos[x]>pos[y]) swap(x,y);if(pos[x]==pos[y]) return;
cov(1,1,n,pos[x]+1,pos[y],val);
}
int main(){
n=read();m=read();
for(int i=1;i<n;++i){
int x=read(),y=read();
data[++num].to=y;data[num].next=h[x];h[x]=num;
data[++num].to=x;data[num].next=h[y];h[y]=num;
}dfs1(1);dfs2(1,1);build(1,1,n);
while(m--){
int x=read(),y=read();docov(x,y,read());
}for(int i=1;i<n;++i){
int x=ask(1,1,n,pos[id[i]]);if(x==inf) puts("-1");
else printf("%d\n",x);
}return 0;
}