10
17
2016
1

UOJ Easy Round #7 题解

毛爷爷已经发过了:链接

我来写一些考试时的感受吧

开考后6min:

T1什么鬼?但是好像不难……

T2什么鬼?答案可以有误差?

T3什么鬼?我只会暴力

开考后10min:

T1没思路啊……弃疗比赛算了

开考后1hr46min:

啊!UOJ比赛不是CF,只要看了题目都计入排行榜!赶快写题不然Rating要掉了!

开考后2hr17min:

哎……T1为啥不是每次向右向下走一格呢?啊!原来走中间时间最短的越长越好而不是直接在当前走!

开考后2hr37min:

提交T1,赶快写T2暴力吧

开考后2hr52min:

T2暴力写完了赶快写T3暴力

开考后3hr3min:

啊!T3暴力刚写完!弃疗算了

最终得分100+50+0

-------------------------

以下为部分题解

A.短路

考虑每个环要么走一格要么走完全部,否则将多余的一步用于时间更少的环显然更优

略微推一下式子就发现可以线性扫描一遍解决

时间复杂度$O(n)$

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;
const long long INF=99999999999999999ll;

int n;
long long a[N],ans,last,sho,lw;

int main(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
scanf("%d",&n);
for(int i=0;i<=n;i++)scanf("%lld",&a[i]);
last=4ll*a[n];
ans=(n*4ll+1)*a[n];
sho=a[n];lw=n;
for(int i=n-1;i>=0;i--){
	if(a[i]<sho){sho=a[i];lw=i;}
	last+=(sho+a[i])*2ll;
	ans=min(ans,last+i*4ll*a[i]-3*a[i]);
	//printf("Aw:%lld %lld\n",ans,last+i*4ll*a[i]-3*a[i]);
}
printf("%lld\n",ans);
return 0;
}

B.天路

订正时发现题目看错了……是与答案相差$5\%$而不是5!

那么每次乘一下1.05就不会出问题了……然后随便把小于枚举值的ans更新一下即可

复杂度我也不太会分析你萌看毛爷爷的解释吧

那个分治现在还不太会……

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=100005,INF=1000005;

int n,a[N],ans[N],mx[N],mn[N],f1,f2,l1,l2;

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline int Calc(int x){
mx[f1=l1=1]=1;
mn[f2=l2=1]=1;
int pos=1;
for(register int i=2;i<=n;i++){
	while(f1<=l1 && a[mx[l1]]<a[i])l1--;
	while(f2<=l2 && a[mn[l2]]>a[i])l2--;
	mx[++l1]=i;mn[++l2]=i;
	while(a[mx[f1]]-a[mn[f2]]>x){
		pos++;
		while(f1<=l1 && mx[f1]<pos)f1++;
		while(f2<=l2 && mn[f2]<pos)f2++;
	}
	ans[i-pos+1]=min(ans[i-pos+1],a[mx[f1]]-a[mn[f2]]);
}
}

inline void Solve(){
for(register int i=0;i<=INF*2;i=(int)(i*1.05)+1)Calc(int(i*1.05));
for(register int i=n-1;i>=2;i--)ans[i]=min(ans[i],ans[i+1]);
for(register int i=2;i<=n;i++)printf("%d\n",ans[i]);
}

int main(){
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
Read(n);
for(register int i=1;i<=n;i++)Read(a[i]),ans[i]=1e9;
if(n<=1000){
	for(register int i=1;i<=n;i++){
		int mx=a[i],mn=a[i];
		for(register int j=i+1;j<=n;j++){
			mx=max(mx,a[j]);mn=min(mn,a[j]);
			ans[j-i+1]=min(ans[j-i+1],mx-mn);
		}
	}
	for(register int i=2;i<=n;i++)printf("%d\n",ans[i]);
}
else Solve();
return 0;
}
Category: 比赛 | Tags: OI uoj
8
16
2016
0

UOJ Round #15 题解

这次比赛我打的很不好……其实是因为懒

没写暴力

当时做掉了A,BC当时不会做,现在也不会做

所以暂时只有A的题解

A.奥林匹克五子棋

我们思考怎么摆放最优

首先我们发现每一行的摆放是否连通只和上一行的摆放方式有关

所以我们要尽量减少连通

想让上下不联通得左右放

想让左右不联通得上下放

那么我们就得到了一种摆放的方式

0101010101

0101010101

1010101010

1010101010

这样就可以完成目标了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

int n,m,k;
queue<pair<int,int> > Q1,Q2;

int Abs(int x){return x>0?x:-x;}

int main(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
if(k==1){puts("-1");return 0;}
else if(k==2){if(n<2 || m<2){if(n==1)for(int i=1;i<=m;i++)printf("%d %d\n",1,i);else if(m==1)for(int i=1;i<=n;i++)printf("%d %d\n",i,1);}else puts("-1");return 0;}
else if(k>min(n,m)){
	for(int i=1;i<=n;i++){
        if(i%2){if(m%2)for(int j=1;j<=m;j++)printf("%d %d\n",i,j);else for(int j=m;j;j--)printf("%d %d\n",i,j);}
        else for(int j=1;j<=m;j++)printf("%d %d\n",i,j);
	}
	return 0;
}
else if(k>2){
	for(int i=1;i<=n;i++){
		if(i%4==1 || i%4==2){for(int j=1;j<=m;j++){if(j&1)Q1.push(make_pair(i,j));else Q2.push(make_pair(i,j));}}
		else {for(int j=1;j<=m;j++){if(j&1)Q2.push(make_pair(i,j));else Q1.push(make_pair(i,j));}}
	}
	if(Abs(Q1.size()-Q2.size())>=2){
		while(!Q1.empty())Q1.pop();
		while(!Q2.empty())Q2.pop();
		swap(n,m);
		for(int i=1;i<=n;i++){
			if(i%4==1 || i%4==2){for(int j=1;j<=m;j++){if(j&1)Q1.push(make_pair(j,i));else Q2.push(make_pair(j,i));}}
			else {for(int j=1;j<=m;j++){if(j&1)Q2.push(make_pair(j,i));else Q1.push(make_pair(j,i));}}
		}
		if(Abs(Q1.size()-Q2.size())>=2){puts("-1");return 0;}
		else {
            int x=n*m,flg=1;
			while(x--){
				if(flg){printf("%d %d\n",Q1.front().first,Q1.front().second);Q1.pop();}
				else {printf("%d %d\n",Q2.front().first,Q2.front().second);Q2.pop();}
				flg^=1;
			}
		}
	}
	else {
		int x=n*m,flg=1;
		while(x--){
			if(flg){printf("%d %d\n",Q1.front().first,Q1.front().second);Q1.pop();}
			else {printf("%d %d\n",Q2.front().first,Q2.front().second);Q2.pop();}
			flg^=1;
		}
	}
	return 0;
}
return 0;
}

B.奥林匹克环城马拉松

正在思考中

C.奥林匹克数据结构

正在思考中

 

Category: 比赛 | Tags: 比赛 OI uoj
8
16
2016
0

Codeforces Round #367 (Div. 2) 题解

订正完了就发一下题解吧

第一次写比赛题解

当时我在比赛时A掉了ABCD,E没敢写链表就GG了

所以我订正完后来发一下

A.Beru-taxi

模拟即可

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

int a,b,n,pos;
double t=21000000000000000.0;

double Dist(int x,int y,int z){return sqrt(1.0*(x-a)*(x-a)+(y-b)*(y-b))/(1.0*z);}

int main(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
scanf("%d %d",&a,&b);
scanf("%d",&n);
for(int i=1;i<=n;i++){
	int tx,ty,s;
	scanf("%d %d %d",&tx,&ty,&s);
    t=min(Dist(tx,ty,s),t);
}
printf("%.6lf\n",t);
return 0;
}

B.Interesting drink

虽然有线性做法但是二分显然更好写吧……那就写二分

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;

int n,a[N],m;

int main(){
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
scanf("%d",&m);
while(m--){
	int x;
	scanf("%d",&x);
    printf("%d\n",upper_bound(a+1,a+n+1,x)-a-1);
}
return 0;
}

C.Hard problem

这不是暴力比较就好了?然后做一个贪心(请无视我的数组名)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;

int n,pos[N];
long long dp[N][2],c[N];
char str[N];

bool Big_Small(int x,int inv1,int y,int inv2){
if(!inv1 && !inv2){
	int px=pos[y];
	for(int i=pos[x];i<pos[x+1];i++,px++){
		if(px>=pos[y+1])return 0;
		if(str[i]<str[px])return 1;
		else if(str[i]>str[px])return 0;
	}
	return 1;
}
if(inv1 && !inv2){
	int px=pos[y];
	for(int i=pos[x+1]-1;i>=pos[x];i--,px++){
		if(px>=pos[y+1])return 0;
		if(str[i]<str[px])return 1;
		else if(str[i]>str[px])return 0;
	}
	return 1;
}
if(!inv1 && inv2){
	int px=pos[y+1]-1;
	for(int i=pos[x];i<pos[x+1];i++,px--){
		if(px<pos[y])return 0;
		if(str[i]<str[px])return 1;
		else if(str[i]>str[px])return 0;
	}
	return 1;
}
if(inv1 && inv2){
	int px=pos[y+1]-1;
	for(int i=pos[x+1]-1;i>=pos[x];i--,px--){
		if(px<pos[y])return 0;
		if(str[i]<str[px])return 1;
		else if(str[i]>str[px])return 0;
	}
	return 1;
}
}

int main(){
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%I64d",&c[i]);
pos[1]=1;
memset(dp,127,sizeof(dp));
for(int i=1;i<=n;i++){
	scanf("%s",str+pos[i]);
	pos[i+1]=strlen(str+1)+1;
}
dp[1][0]=0;dp[1][1]=c[1];
for(int i=2;i<=n;i++){
	if(Big_Small(i-1,0,i,0))dp[i][0]=min(dp[i-1][0],dp[i][0]);
	if(Big_Small(i-1,0,i,1))dp[i][1]=min(dp[i-1][0]+c[i],dp[i][1]);
	if(Big_Small(i-1,1,i,0))dp[i][0]=min(dp[i-1][1],dp[i][0]);
	if(Big_Small(i-1,1,i,1))dp[i][1]=min(dp[i-1][1]+c[i],dp[i][1]);
}
long long px=min(dp[n][0],dp[n][1]);
printf("%I64d\n",px>=21000000000000000ll?-1ll:px);
return 0;
}

D.Vasiliy's Multiset

字典树裸题……没有任何难度

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200005;

int n,x,st[32],cnt=1;
char str[10];

struct Trie{
int ch[2],num;
}tree[7000005];

void Num(int x){
for(int i=31;i>=0;i--)st[i+1]=(x&(1<<i))>=1;
}

void Add(){
int rt=1;
for(int i=32;i;i--){
	if(!tree[rt].ch[st[i]])tree[rt].ch[st[i]]=++cnt;
	tree[tree[rt].ch[st[i]]].num++;
	rt=tree[rt].ch[st[i]];
}
}

void Del(){
int rt=1;
for(int i=32;i;i--){
	if(!tree[rt].ch[st[i]])tree[rt].ch[st[i]]=++cnt;
	tree[tree[rt].ch[st[i]]].num--;
	rt=tree[rt].ch[st[i]];
}
}

int Ask(){
int rt=1;
for(int i=32;i;i--){
	if(tree[tree[rt].ch[!st[i]]].num){rt=tree[rt].ch[!st[i]];st[i]=1;}
	else if(tree[tree[rt].ch[st[i]]].num){rt=tree[rt].ch[st[i]];st[i]=0;}
	else {break;}
}
int x=0;
for(int i=1;i<=32;i++){x|=(st[i]<<(i-1));/*printf("%d\n",x);*/}
return x;
}

int main(){
freopen("D.in","r",stdin);
freopen("D.out","w",stdout);
scanf("%d",&n);
Add();
while(n--){
	int x;
	scanf("%s %d",str,&x);
    Num(x);
    //for(int i=32;i;i--)printf("%d ",st[i]);
	//putchar('\n');
    if(str[0]=='+')Add();
	if(str[0]=='-')Del();
	if(str[0]=='?')printf("%d\n",Ask());
}
return 0;
}

E.Working routine

使用十字链表维护整个矩阵,每次修改只改边缘的就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1005;

int n,m,mat[N][N],q;

struct Value{
Value *up,*down,*left,*right;
int v;
Value(int x){up=down=left=right=NULL;v=x;}
}*root[N],*Upx[N],*Upy[N],*Downx[N],*Downy[N],*Leftx[N],*Lefty[N],*Rightx[N],*Righty[N];

inline void Initialize(){
for(int i=1;i<=n;i++){
	Value *tp;
	for(int j=1;j<=m;j++){
		if(j==1){
			root[i]=new Value(mat[i][j]);
			tp=root[i];
		}
		else {
			tp->right=new Value(mat[i][j]);
			tp->right->left=tp;
            tp=tp->right;
		}
	}
}
}

inline void Build(){
Value *tp[N];
tp[0]=tp[n+1]=NULL;
for(int i=1;i<=n;i++)tp[i]=root[i];
for(int i=1;i<=m;i++){
	for(int j=1;j<=n;j++){tp[j]->up=tp[j-1];tp[j]->down=tp[j+1];}
	for(int j=1;j<=n;j++)tp[j]=tp[j]->right;
}
}

inline void SelectX(Value *r[N],int x,int y,int len){
Value *tp=root[x];
for(int i=1;i<y;i++)tp=tp->right;
for(int i=1;i<=len;i++){r[i]=tp;tp=tp->right;}
}

inline void SelectY(Value *r[N],int x,int y,int len){
Value *tp=root[x];
for(int i=1;i<y;i++)tp=tp->right;
for(int i=1;i<=len;i++){r[i]=tp;tp=tp->down;}
}

inline void PrintMatrix(){
for(int i=1;i<=n;i++){
	Value *cur;
	for(int j=1;j<=m;j++){
		if(j==1)cur=root[i];
		else cur=cur->right;
		printf("%d ",cur->v);
	}
	putchar('\n');
}
}

inline void Change(int l1,int r1,int l2,int r2,int h,int w){
Value *tp;
SelectX(Upx,l1,r1,w);
SelectX(Upy,l2,r2,w);
SelectX(Downx,l1+h-1,r1,w);
SelectX(Downy,l2+h-1,r2,w);
SelectY(Leftx,l1,r1,h);
SelectY(Lefty,l2,r2,h);
SelectY(Rightx,l1,r1+w-1,h);
SelectY(Righty,l2,r2+w-1,h);
//for(int i=1;i<=h;i++)printf("%d ",Leftx[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Lefty[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Rightx[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Righty[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Upx[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Upy[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Downx[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Downy[i]->v);
//putchar('\n');
for(int i=1;i<=h;i++){
    if(Leftx[i]->left && Lefty[i]->left){Leftx[i]->left->right=Lefty[i];Lefty[i]->left->right=Leftx[i];tp=Leftx[i]->left;Leftx[i]->left=Lefty[i]->left;Lefty[i]->left=tp;}
    else if(Leftx[i]->left && !Lefty[i]->left){Lefty[i]->left=Leftx[i]->left;Leftx[i]->left->right=Lefty[i];Leftx[i]->left=NULL;root[l2+i-1]=Leftx[i];}
    else if(!Leftx[i]->left && Lefty[i]->left){Leftx[i]->left=Lefty[i]->left;Lefty[i]->left->right=Leftx[i];Lefty[i]->left=NULL;root[l1+i-1]=Lefty[i];}
    else if(!Leftx[i]->left && !Lefty[i]->left){root[l1+i-1]=Lefty[i];root[l2+i-1]=Leftx[i];}
	if(Rightx[i]->right && Righty[i]->right){Rightx[i]->right->left=Righty[i];Righty[i]->right->left=Rightx[i];tp=Rightx[i]->right;Rightx[i]->right=Righty[i]->right;Righty[i]->right=tp;}
    else if(Rightx[i]->right && !Righty[i]->right){Righty[i]->right=Rightx[i]->right;Rightx[i]->right->left=Righty[i];Rightx[i]->right=NULL;}
    else if(!Rightx[i]->right && Righty[i]->right){Rightx[i]->right=Righty[i]->right;Righty[i]->right->left=Rightx[i];Righty[i]->right=NULL;}
}
for(int i=1;i<=w;i++){
	if(Upx[i]->up && Upy[i]->up){Upx[i]->up->down=Upy[i];Upy[i]->up->down=Upx[i];tp=Upx[i]->up;Upx[i]->up=Upy[i]->up;Upy[i]->up=tp;}
    else if(Upx[i]->up && !Upy[i]->up){Upx[i]->up->down=Upy[i];Upy[i]->up=Upx[i]->up;Upx[i]->up=NULL;}
    else if(!Upx[i]->up && Upy[i]->up){Upx[i]->up=Upy[i]->up;Upy[i]->up->down=Upx[i];Upy[i]->up=NULL;}
	if(Downx[i]->down && Downy[i]->down){Downx[i]->down->up=Downy[i];Downy[i]->down->up=Downx[i];tp=Downx[i]->down;Downx[i]->down=Downy[i]->down;Downy[i]->down=tp;}
    else if(Downx[i]->down && !Downy[i]->down){Downy[i]->down=Downx[i]->down;Downx[i]->down->up=Downy[i];Downx[i]->down=NULL;}
    else if(!Downx[i]->down && Downy[i]->down){Downx[i]->down=Downy[i]->down;Downy[i]->down->up=Downx[i];Downy[i]->down=NULL;}
}
}

int main(){
freopen("E.in","r",stdin);
freopen("E.out","w",stdout);
scanf("%d %d %d",&n,&m,&q);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&mat[i][j]);
Initialize();
Build();
while(q--){
	int l1,r1,l2,r2,h,w;
    scanf("%d %d %d %d %d %d",&l1,&r1,&l2,&r2,&h,&w);
    Change(l1,r1,l2,r2,h,w);
}
PrintMatrix();
return 0;
}

这次Div2真是水的可怕……

 

Category: 比赛 | Tags: OI 比赛

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com