首页
登录 | 注册

2016-2017 ACM-ICPC, NEERC, Moscow Subregional Contest

A. Altitude

从小到大加入每个数,用set查找前驱和后继即可。

时间复杂度$O(n\log n)$。

#include <bits/stdc++.h>
using namespace std ;
const int Maxn=100020,Inf=1e9;
typedef pair<int,int>pi;
int n;
int a[Maxn];
vector<pi>V;
set<int>S;
int ans,rep1,rep2,rep3;
int caldis(int x,int y){
	return y>x?(y-x):(y+n-x);
}
void ask(int loc){
	if(!S.size())return ;
	set<int>::iterator it=S.lower_bound(loc);
	set<int>::iterator it2=it;
	for(int i=0;i<2;i++){
		if(it2==S.begin()){it2=S.end();it2--;}
		else it2--;
	}
	int ret1=Inf,ret2=Inf,cs1,cs2;
	for(int i=0;i<5;i++){
		int t1=caldis(*it2,loc);
		int t2=caldis(loc,*it2);
		if(t1<ret1){cs1=*it2;ret1=t1;}
		if(t2<ret2){cs2=*it2;ret2=t2;}
		it2++;
		if(it2==S.end())it2=S.begin();
	}
	if(ret1+ret2<ans){rep1=cs1;rep2=loc;rep3=cs2;ans=ret1+ret2;}
	return ;
}
int main () {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",a+i),V.push_back(pi(a[i],i));
	sort(V.begin(),V.end());
	ans=Inf;
	for(int i=0,j;i<V.size();i=j){
		for(j=i;j<V.size();j++){
			if(V[j].first!=V[i].first)break;
			ask(V[j].second);
		}
		for(int k=i;k<j;k++){
			S.insert(V[k].second);
		}
	}
	printf("%d %d %d\n",rep1,rep2,rep3);
	return 0 ;
}

  

B. Blocking Buffer

观察发现$\gcd(r,w)$都是可以达到的,于是欧几里得求一下即可。

#include <bits/stdc++.h>
using namespace std ;
const int Maxn=200020,Inf=1e9;
typedef pair<int,int>pi;
typedef long long LL;
bool solve(LL l,LL A,LL B){
	if(l-B>=A-1)return 0;
	LL gc=__gcd(A,B);
	LL tmp=(l-B)/gc*gc;
	while(tmp<=l-B)tmp+=gc;
	if(tmp<A)return 1;
	return 0;
}
int main () {
	LL l,A,B;
	while(cin>>l>>A>>B){
	/*
	set<LL>S;
	LL cur=0;
	bool flag=1;
	S.insert(0);
	while(1){
		if(cur>l-B&&cur<A){
			flag=0;
			break;
		}
		if(cur>=A){
			cur%=A;
		}
		else{
			cur=(l-cur)/B*B+cur;
		}
		if(S.find(cur)!=S.end()){break;}
	}
	puts(flag?"OK":"DEADLOCK");
	*/
	puts(solve(l,A,B)?"DEADLOCK":"OK");
	}
	return 0 ;
}

  

C. Catch Me If You Can

留坑。

 

D. Demolition Time

留坑。

 

E. Economy Printing

将数字从小到大排序,那么第$i$个数要么自己作为开头,要么和$i-2$连接,要么和$i-1$连接,设$f[i][j][k]$表示考虑了前$i$个数,第$i-1$个数用操作$j$,第$i$个数用操作$k$时的最小串长,然后DP即可。

时间复杂度$O(n\log n)$。

#include <bits/stdc++.h>
using namespace std ;

typedef pair < int , int > pii ;

#define clr( a , x ) memset ( a , x, sizeof a )

const int MAXN = 200005 ;
const int INF = 0x3f3f3f3f ;
int n ;

int len[MAXN] ;
int a[MAXN] ;
int dp[MAXN][4][4] ;
int f[MAXN] ;
pii p[MAXN][4][4] ;
int vis[MAXN] ;

int calc ( int x ) {
	int t = 0 ;
	while ( x ) {
		t ++ ;
		x /= 10 ;
	}
	return t ;
}

void dfs ( int n , int x , int y ) {
	if ( n == 1 ) return ;
	int nx = p[n][x][y].first ;
	int ny = x ;
	f[n] = p[n][x][y].second ;
	dfs ( n - 1 , nx , ny ) ;
}

int dfs2 ( int x ) {
	vis[x] = 1 ;
	if ( f[x] == 0 ) return x ;
	return dfs2 ( f[x] ) ;
}	

void solve () {
	for ( int i = 1 ; i <= n ; ++ i ) {
		scanf ( "%d" , &a[i] ) ;
	}
	sort ( a + 1 , a + n + 1 ) ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		len[i] = calc ( a[i] ) ;
	}
	clr ( f , 0 ) ;
	clr ( p , 0 ) ;
	clr ( dp , INF ) ;
	dp[0][0][0] = 0 ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		for ( int j = 0 ; j < 4 ; ++ j ) {
			for ( int k = 0 ; k < 4 ; ++ k ) if ( dp[i - 1][j][k] != INF ) {
				for ( int l = 0 ; l < 4 ; ++ l ) {
					int tmp = dp[i - 1][j][k] + 1 + len[i] ;
					if ( l ) tmp = tmp + 1 + len[i] ;
					if ( l == 1 && a[i] % 2 == 0 ) continue ;
					if ( l == 2 && a[i] % 2 == 1 ) continue ;
					if ( dp[i][k][l] > tmp ) {
						dp[i][k][l] = tmp ;
						p[i][k][l] = pii ( j , 0 ) ;
					}
				}
				if ( j == 1 || j == 2 ) {
					if ( i > 2 && a[i] - a[i - 2] == 2 ) {
						int tmp = dp[i - 1][j][k] + len[i] - len[i - 2] ;
						if ( dp[i][k][j] > tmp ) {
							dp[i][k][j] = tmp ;
							p[i][k][j] = pii ( j , i - 2 ) ;
						}
					}
				}
				if ( k == 1 || k == 2 ) {
					if ( i > 1 && a[i] - a[i - 1] == 2 ) {
						int tmp = dp[i - 1][j][k] + len[i] - len[i - 1] ;
						if ( dp[i][k][k] > tmp ) {
							dp[i][k][k] = tmp ;
							p[i][k][k] = pii ( j , i - 1 ) ;
						}
					}
				}
				if ( k == 3 ) {
					if ( i > 1 && a[i] - a[i - 1] == 1 ) {
						int tmp = dp[i - 1][j][k] + len[i] - len[i - 1] ;
						if ( dp[i][k][k] > tmp ) {
							dp[i][k][k] = tmp ;
							p[i][k][k] = pii ( j , i - 1 ) ;
						}
					}
				}
			}
		}
	}
	int ans = INF , x = -1 , y = -1 ;
	for ( int i = 0 ; i < 4 ; ++ i ) {
		for ( int j = 0 ; j < 4 ; ++ j ) {
			if ( dp[n][i][j] < ans ) {
				ans = dp[n][i][j] ;
				x = i ;
				y = j ;
			}
		}
	}
	dfs ( n , x , y ) ;
	//printf ( "%d\n" , ans - 1 ) ;
	clr ( vis , 0 ) ;
	int flag = 0 ;
	for ( int i = n ; i >= 1 ; -- i ) if ( !vis[i] ) {
		int L = dfs2 ( i ) ;
		if ( flag ) putchar ( ',' ) ;
		flag = 1 ;
		if ( L == i ) printf ( "%d" , a[i] ) ;
		else {
			printf ( "%d" , a[L] ) ;
			if ( a[i] - a[f[i]] == 2 ) {
				if ( a[i] % 2 == 0 ) putchar ( '%' ) ;
				else putchar ( '#' ) ;
			} else putchar ( '-' ) ;
			printf ( "%d" , a[i] ) ;
		}
	}
	puts ( "" ) ;
}

int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}

  

F. Format

枚举有没有"^"符号,然后将字符分成三类:可选可不选、必须要选、必须不能选。

设$f[i]$表示处理完字典序最小的$i$个字符时的最短串长以及对应串长的字典序最小串,然后枚举往前延伸到哪里转移。

需要注意的是,如果全部字符都出现了,那么答案应该是%[^!],需要特判。

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
typedef pair<int,string>P;
const int N=300;
int n,i,j,v[N];char s[222222];
P ans(N,""),f[N];
inline bool check(char x){
  if(x==' ')return 1;
  if(x>='0'&&x<='9')return 1;
  if(x>='a'&&x<='z')return 1;
  if(x>='A'&&x<='Z')return 1;
  return 0;
}
void dp(){
 for(i=32;i<=126;i++){
    f[i]=P(N,"");
    if(v[i]==0||v[i]==2){
      P t=f[i-1];
      f[i]=t;
    }
    if(v[i]==0||v[i]==1){
      for(j=i;j>=32;j--){
        if(v[j]==2)break;
        P t=f[j-1];
        if(j==i){
          t.first++;
          t.second.push_back(char(i));
	}else if(j+1==i){
	  t.first+=2;
	  t.second.push_back(char(j));
          t.second.push_back(char(i));
	}else{
	  t.first+=3;
	  t.second.push_back(char(j));
	  t.second+="-";
          t.second.push_back(char(i));
	}
	f[i]=min(f[i],t);
      }
    }
  }
}
int main(){
  fgets(s,111111,stdin);
  n=strlen(s);
  //0 : can choose and can not choose
  //1 : must choose
  //2 : mustn't choose
  for(i=32;i<=126;i++)v[i]=0;
  for(i=0;i<n;i++)if(check(s[i]))v[s[i]]=1;
  for(i=32;i<=126;i++)if(!v[i]&&check(i))v[i]=2;
  f[31]=P(0,"%[");
  dp();
  ans=f[126];
  for(i=32;i<=126;i++)v[i]=0;
  for(i=0;i<n;i++)if(check(s[i]))v[s[i]]=2;
  for(i=32;i<=126;i++)if(!v[i]&&check(i))v[i]=1;
  f[31]=P(1,"%[^");
  dp();
  if(f[126].first>1)ans=min(ans,f[126]);else ans=min(ans,P(2,"%[^!"));
  ans.second+="]";
  cout<<ans.second<<endl;
  return 0;
}

  

G. Great Guest Gathering

分成$n$轮构造即可。

#include <bits/stdc++.h>
using namespace std ;

int n ;

void solve () {
	printf ( "%d %d %d\n" , 1 , 1 , 0 ) ;
	for ( int i = 1 ; i < n ; ++ i ) {
		for ( int j = i + 2 ; j <= n ; ++ j ) {
			printf ( "%d %d %d\n" , j , j , i ) ;
			printf ( "%d %d %d\n" , i , i , j ) ;
		}
		printf ( "%d %d %d\n" , i + 1 , i + 1 , i ) ;
	}
	for ( int i = n - 1 ; i >= 2 ; -- i ) {
		printf ( "%d %d %d\n" , i , i , i + 1 ) ;
	}
	printf ( "%d %d %d\n" , 0 , 1 , 2 ) ;
}

int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}

  

H. Hockey Cup

按题意模拟即可。

#include <bits/stdc++.h>
using namespace std ;
const int Maxn=200020,Inf=1e9;
typedef pair<int,int>pi;
typedef long long LL;
map<string,int>Mp;

string ts[]={"Russia","Sweden","Finland","NA"};
int res[4][4][3];
int sc[4][6];
int g[4][4];
int cmpop;
bool cmp(int a,int b){
	return sc[a][cmpop]>sc[b][cmpop];
}
void solve(vector<int>&v,int ty){
	if(v.size()<=2){
		if(v.size()==1)return ;
		if(v.size()==2){
			if(!g[v[0]][v[1]])swap(v[0],v[1]);
		}
		return ;
	}
	cmpop=ty;
	sort(v.begin(),v.end(),cmp);
	vector<int>rv;
	for(int i=0,j;i<v.size();i=j){
		vector<int>tmp;
		for(j=i;j<v.size();j++){
			if(sc[v[j]][ty]!=sc[v[i]][ty]){break;}
			tmp.push_back(v[j]);
		}
		solve(tmp,ty+1);
		for(int it=0;it<tmp.size();it++)rv.push_back(tmp[it]);
	}
	swap(rv,v);
}
int go(){
	vector<int>v;
	for(int i=0;i<4;i++)v.push_back(i);
	solve(v,0);
	if(!v[0]||!v[1])return 1<<1;
	return 1<<0;
}
int check(){
	memset(sc,0,sizeof sc);
	int ret=0;
	for(int i=0;i<4;i++){
		for(int j=i+1;j<4;j++){
			int t1=res[i][j][0],t2=res[i][j][1];
			int t3=res[i][j][2];
			int ti=i,tj=j;
			g[i][j]=1;g[j][i]=0;
			if(t1<t2){
				g[i][j]=0;g[j][i]=1;
				swap(ti,tj);
				swap(t1,t2);
			}
			sc[ti][0]+=2;
			sc[ti][1]++;
			if(!t3)sc[ti][2]++;
			sc[ti][3]+=t1-t2;
			sc[ti][4]+=t1;
			if(t3)sc[tj][0]++;
			sc[tj][3]-=t1-t2;
			sc[tj][4]+=t2;
		}
	}
	int tmp[10];
	for(int i=0;i<4;i++)tmp[i]=i;
	do{
		for(int i=0;i<4;i++)sc[i][5]=tmp[i];
		ret|=go();
	}while(next_permutation(tmp,tmp+4));
	return ret;
}
int main () {
	for(int i=0;i<4;i++)Mp[ts[i]]=i;
	string name1,name2;
	for(int i=0;i<5;i++){
		string name1,name2;
		char ss[10];
		int t1,t2,t3;
		cin>>name1>>name2>>t1>>t2;
		fgets(ss,sizeof ss,stdin);
		if(strlen(ss)>=2){
			t3=1;
		}
		else t3=0;
		int id1=Mp[name1],id2=Mp[name2];
		if(id1>id2){swap(t1,t2);swap(id1,id2);}
		res[id1][id2][0]=t1;
		res[id1][id2][1]=t2;
		res[id1][id2][2]=t3;
	}
	cin>>name1>>name2;
	int id1=Mp[name1],id2=Mp[name2];
	int ans=0;
	if(id1>id2)swap(id1,id2);
	for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			if(i==j)continue;
			res[id1][id2][0]=i;
			res[id1][id2][1]=j;
			res[id1][id2][2]=0;
			ans|=check();
			if(abs(i-j)==1){
				res[id1][id2][2]=1;
				ans|=check();
			}
		}
	}
	if(ans==3)puts("Believe in playoff!");
	else if(ans==2)puts("Already in playoff!");
	else puts("No chance");
	return 0 ;
}

  

I. Interesting Interactive Idea

留坑。

 

J. Juice Degustation

留坑。

 

K. Knights of the Old Republic

考虑对图做集合DP,设$f[S]$表示占领S集合的最小代价,考虑从小到大加入每条边,加入每条边时,如果形成环,那么显然可以扔掉。

否则$f[S]=\min(f[A]+f[B],\min(A中费用最小的点,B中费用最小的点)\times\max(A中需求最大的点,B中需求最大的点,当前边权))$。

在Kruskal的时候用并查集维护即可。

时间复杂度$O(m\log m)$。

#include <bits/stdc++.h>
using namespace std ;

typedef long long LL ;

const int MAXN = 300005 ;

struct Edge {
	int u , v , c ;
	bool operator < ( const Edge& a ) const {
		return c < a.c ;
	}
} ;

Edge E[MAXN] ;
int a[MAXN] , b[MAXN] , p[MAXN] ;
LL sum[MAXN] ;
int n , m ;

int F ( int x ) {
	return p[x] == x ? x : ( p[x] = F ( p[x] ) ) ;
}

void solve () {
	for ( int i = 1 ; i <= n ; ++ i ) {
		p[i] = i ;
	}
	for ( int i = 1 ; i <= n ; ++ i ) {
		scanf ( "%d%d" , &a[i] , &b[i] ) ;
		sum[i] = 1LL * a[i] * b[i] ;
	}
	for ( int i = 0 ; i < m ; ++ i ) {
		scanf ( "%d%d%d" , &E[i].u , &E[i].v , &E[i].c ) ;
	}
	sort ( E , E + m ) ;
	for ( int i = 0 ; i < m ; ++ i ) {
		int x = F ( E[i].u ) ;
		int y = F ( E[i].v ) ;
		if ( x == y ) continue ;
		int na = max ( max ( a[x] , a[y] ) , E[i].c ) ;
		int nb = min ( b[x] , b[y] ) ;
		LL tmp = 1LL * na * nb ;
		sum[y] = min ( sum[x] + sum[y] , tmp ) ;
		p[x] = y ;
		a[y] = na ;
		b[y] = nb ;
	}
	LL ans = 0 ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		if ( F ( i ) == i ) ans += sum[i] ;
	}
	printf ( "%lld\n" , ans ) ;
}

int main () {
	while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ;
	return 0 ;
}

  

L. Lazy Coordinator

从后往前处理,维护当前时刻到每个时刻被选用的概率乘以时刻之和,减去当前出题人报名的时间即可。

时间复杂度$O(n)$。

#include <bits/stdc++.h>
using namespace std ;
const int Maxn=200020,Inf=1e9;
typedef pair<int,int>pi;
int n;
int arr[Maxn];
char op[Maxn];
int tl[Maxn],has[Maxn],idx[Maxn];
double ans[Maxn];
int main () {
	scanf("%d",&n);
	int cnt=0,id=0;
	for(int i=1;i<=n*2;i++){
		scanf(" %c%d",&op[i],&tl[i]);
		idx[i]=-1;
		if(op[i]=='+'){
			id++;
			arr[id]=tl[i];
			idx[i]=id;
			cnt++;
		}
		else{
			cnt--;
		}
		has[i]=cnt;
	}
	double sum=0;
	for(int i=n*2;i>=1;i--){
		if(op[i]=='-'){
			int k=has[i]+1;
			sum=sum*(1.0-1.0/k)+tl[i]*(1.0/k);
		}
		else ans[idx[i]]=sum;
	}
	for(int i=1;i<=n;i++)printf("%.12f\n",ans[i]-arr[i]);
	return 0 ;
}

  


总结:

  • E题思考方向错了,在错误的道路上越走越远,以致最后半小时想出正解却没有时间写完。
  • G题poursoul没过样例就自信提交,导致在样例WA,下次要注意。

 


相关文章

  • 为什么说 Java 程序员到了必须掌握 Spring Boot 的时候?
    Spring Boot 2.0 的推出又激起了一阵学习 Spring Boot 热,就单从我个人的博客的访问量大幅增加就可以感受到大家对学习 Spring Boot 的热情,那么在这么多人热衷于学习 Spring Boot 之时,我自己也在 ...
  • Spring的历史及哲学
    Spring的历史和哲学 1.Spring 历史 时间回到2002年,当时正是 Java EE 和 EJB 大行其道的时候,很多知名公司都是采用此技术方案进行项目开发.这时候有一个美国的小伙子认为 EJB 太过臃肿,并不是所有的项目都需要使 ...
  • 使用 ASP.NET Core MVC 创建 Web API(五)
    使用 ASP.NET Core MVC 创建 Web API 使用 ASP.NET Core MVC 创建 Web API(一) 使用 ASP.NET Core MVC 创建 Web API(二)  使用 ASP.NET Core MVC ...
  • Python是什么? Python 是一种面向对象的解释型计算机程序设计语言,由荷兰人Guido van Rossum于1989年发明,第一个公开发行版发行于1991年. Python是纯粹的自由软件, 源代码和解释器CPython遵循 G ...
  • Entity Framework Core in Action Entityframework Core in action是 Jon P smith 所著的关于Entityframework Core 书籍.原版地址. 是除了官方文档外另 ...
  • Entity Framework Core in Action Entityframework Core in action是 Jon P smith 所著的关于Entityframework Core 书籍.原版地址. 是除了官方文档外另 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.074 s.
京ICP备10005923号