5
14
2019
2

2019黑龙江省赛游记

其实没啥好写的。。。

银牌第一，差一个罚时or一道题

cycleke队rk5，练习生队rk2，TOM队rk1

端茶倒水三人组集体没带板子，裸费用流打不出来

OI积累的实力已经归零了

Category: 大学 | Tags: 比赛 随笔
3
30
2019
0

CCCC2019参赛感想

今天我参加了CCCC2019(团体程序天梯赛)，头一次代表HIT参赛(虽然有3个队)，写点感想。

早上八点多起来，九点多搭上一班公交赶到一区，差点迟到(9:40集合)，赶到之后就和大佬们一块坐地铁到哈理工了

到了哈理工之后拍照吃饭，上的菜太多根本吃不完，不过月底没钱，这种免费蹭饭机会不能错过

然后就考试了……从L1-1一直做到了L1-7，十分顺利

然后就是坑爹的L1-8，字符串题，调了30min以上……

最后剩一小时了，赶快赶L2的题，做了L2-1 L2-3 L2-4，还剩20min

看了5min的L2-2和L3-1的题，感觉L2-2就是个裸的哈希+倍增LCA，赶快写

时间到了，我哈希部分倒是写完了，LCA没写于是没办法，手速太慢了

最后和几个大佬搭乘地铁回了一区，吃了顿饭之后回二区，比赛就结束了……

最后搞了175分，不是特别满意，不过这场比赛能拿满分的吉利大爷是真的强——orzorzorz

后面还有四省赛，估计也能去蹭饭，不知道到时候会不会有所提升

Category: 随笔 | Tags: 比赛 随笔
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