[破碎的状态] [-48] 北大夏令营 Day 1
absi2011
posted @ Jun 04, 2016 09:44:53 PM
in OI系列
with tags
NOI POJ 小高考 JSOI NOIP 字符串 DP 模拟 dijkstra BFS 线段树 搜索 DFS AC自动机 瞎搞 pku
, 713 阅读
早上他们说了一堆东西..
然后..那些东西暂时无视
反正..我现在是来签约的
早上:http://bailian.openjudge.cn/oitraining2016a/
========
开场
看到B题是a*b 问题仔细看了下是FFT版,弃疗..
看D题是个分形的好题
dfs了下..
WA!
发现被回车问题坑了一发
再交
WA!
数组开小了TAT
再交
AC!一血!
*题意:给你个n,求打印一个n阶的这样的三角形
n<=10
....并没啥用....罚了4次时
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<time.h>
#include<string>
#include<vector>
#include<memory>
#include<bitset>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[2005][3005];
void dfs(int n,int sx,int sy)
{
if (n==1)
{
a[sx][sy+1]='/';
a[sx][sy+2]='\\';
a[sx+1][sy]='/';
a[sx+1][sy+1]='_';
a[sx+1][sy+2]='_';
a[sx+1][sy+3]='\\';
return;
}
dfs(n-1,sx,sy+(1<<(n-1)));
dfs(n-1,sx+(1<<(n-1)),sy);
dfs(n-1,sx+(1<<(n-1)),sy+(1<<n));
}
int main()
{
#ifdef absi2011
freopen("output.txt","w",stdout);
#endif
int flag=0;
for (;;)
{
memset(a,' ',sizeof(a));
int n;
scanf("%d",&n);
if (n==0) return 0;
if (flag==1)
{
putchar('\n');
}
flag=1;
dfs(n,0,0);
int i;
for (i=0;i<(1<<n);i++)
{
int j;
for (j=0;j<i+(1<<n)+1;j++)
{
putchar(a[i][j]);
}
putchar('\n');
}
}
}
然后再接着看
E题似乎是个挺长的题面
AC两题有人交没人过
想了想,看C
不会做..
看A
不会做..
抱着"反正这次是来玩玩的"的心态
所以就写了个暴搜
TLE!
优化一发
AC..又是个一血!
*题意:
给你一个#字形的东西,你要在尽量少的步数内(如果步数一样字典序最小)操作,每次操作如图所示
具体的输入格式可以见题面..
要求中间的8个数字相同,求方案
所以..
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<time.h>
#include<string>
#include<vector>
#include<memory>
#include<bitset>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int af[15]={0,2,6,11,15,20,22,24}; //a : <--
int be[15]={1,3,8,12,17,21,23,24}; //b : <--
int ch[15]={4,5,6,7,8,9,10,24}; //c : -->
int dg[15]={13,14,15,16,17,18,19,24};//d : -->
int center[15]={6,7,8,11,12,15,16,17};
char ans[25];
int a[25];
void oper(int x)
{
if (x==0)
{
a[24]=a[af[0]];
int i;
for (i=0;i<7;i++)
{
a[af[i]]=a[af[i+1]];
}
}
if (x==1)
{
a[24]=a[be[0]];
int i;
for (i=0;i<7;i++)
{
a[be[i]]=a[be[i+1]];
}
}
if (x==2)
{
int i;
int t=a[ch[6]];
for (i=6;i>0;i--)
{
a[ch[i]]=a[ch[i-1]];
}
a[ch[0]]=t;
}
if (x==3)
{
int i;
int t=a[dg[6]];
for (i=6;i>0;i--)
{
a[dg[i]]=a[dg[i-1]];
}
a[dg[0]]=t;
}
if (x==4)
{
int i;
int t=a[be[6]];
for (i=6;i>0;i--)
{
a[be[i]]=a[be[i-1]];
}
a[be[0]]=t;
}
if (x==5)
{
int i;
int t=a[af[6]];
for (i=6;i>0;i--)
{
a[af[i]]=a[af[i-1]];
}
a[af[0]]=t;
}
if (x==6)
{
a[24]=a[dg[0]];
int i;
for (i=0;i<7;i++)
{
a[dg[i]]=a[dg[i+1]];
}
}
if (x==7)
{
a[24]=a[ch[0]];
int i;
for (i=0;i<7;i++)
{
a[ch[i]]=a[ch[i+1]];
}
}
}
int find_ans=0;
int anti[15]={5,4,7,6,1,0,3,2};
void dfs(int x,int y,int last_oper=-1)
{
if (x==y)
{
int val=a[center[0]];
int i;
for (i=1;i<8;i++)
{
if (a[center[i]]!=val) return;
}
find_ans=1;
return;
}
if (x==y+1)
{
if ((a[7]!=a[11])||(a[11]!=a[16])||(a[16]!=a[12])) return;
}
int i;
for (i=0;i<8;i++)
{
ans[y]='A'+i;
if (last_oper==anti[i]) continue;
oper(i);
dfs(x,y+1,i);
if (find_ans==1) return;
oper(anti[i]);
}
}
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
for (;;)
{
scanf("%d",&a[0]);
if (a[0]==0) return 0;
int i;
for (i=1;i<24;i++)
{
scanf("%d",&a[i]);
}
find_ans=0;
for (i=0;;i++)
{
dfs(i,0);
if (find_ans)
{
if (i==0)
{
printf("No moves needed\n");
}
else
{
ans[i]=0;
printf("%s\n",ans);
}
printf("%d\n",a[6]);
break;
}
}
}
}
我就接着来看别的题
B题很显然放弃
C题不会,读E题去
看起来是个dp
*题意:
两个人彼此憎恨,所以他们希望离得越远越好
他们俩住在一个n*n的方格里,一个要从H到S,一个要从h到s
这天,他们俩从家到学校,你要构造他们俩走路的一个方案,使得他们距离最小的时刻距离最大
PS:图上有障碍物
PS:H和S对于h出发的人不可到达,同理h和s对于H出发的人不可到达
n<=30
感觉..是个dp的好题啊
随便dp了一发
WA!
回车问题..重新弄一下
WA!
唉?哪里有错?
那..再修改下回车问题
WA!
等下!H对于h不可到达?
居然没看到这条件
WA!
等下S也不可到达?
AC!
呼呼..
又是一血..
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<time.h>
#include<string>
#include<vector>
#include<memory>
#include<bitset>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int dp[1500625];
int pre[1500625];
bool visit[1500625];
char a[35][35];
int code(int x,int y,int z,int w)
{
return (((x*35+y)*35+z)*35+w);
}
int dist(int x,int y,int z,int w)
{
return ((z-x)*(z-x))+((y-w)*(y-w));
}
int dire[5][2]={
{0,1},
{0,-1},
{-1,0},
{1,0},
{0,0}};
void dfs1(int x1,int y1,int x2,int y2)
{
int t=pre[code(x1,y1,x2,y2)];
if (t==-1) return;
int nowx1,nowx2,nowy1,nowy2;
nowy2=t%35;
t/=35;
nowx2=t%35;
t/=35;
nowy1=t%35;
t/=35;
nowx1=t;
dfs1(nowx1,nowy1,nowx2,nowy2);
if ((nowx1==x1-1)) printf("S");
if ((nowx1==x1+1)) printf("N");
if ((nowy1==y1-1)) printf("E");
if ((nowy1==y1+1)) printf("W");
}
void dfs2(int x1,int y1,int x2,int y2)
{
int t=pre[code(x1,y1,x2,y2)];
if (t==-1) return;
int nowx1,nowx2,nowy1,nowy2;
nowy2=t%35;
t/=35;
nowx2=t%35;
t/=35;
nowy1=t%35;
t/=35;
nowx1=t;
dfs2(nowx1,nowy1,nowx2,nowy2);
if ((nowx2==x2-1)) printf("S");
if ((nowx2==x2+1)) printf("N");
if ((nowy2==y2-1)) printf("E");
if ((nowy2==y2+1)) printf("W");
}
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
int flag=0;
for (;;)
{
scanf("%d",&n);
if (n==0) return 0;
if (flag) printf("\n");
flag=1;
int i;
int sx1,sy1,sx2,sy2,ex1,ey1,ex2,ey2;
memset(visit,false,sizeof(visit));
memset(dp,-1,sizeof(dp));
for (i=0;i<n;i++)
{
scanf("%s",a[i]);
int j;
for (j=0;j<n;j++)
{
if (a[i][j]=='H')
{
sx1=i;
sy1=j;
}
if (a[i][j]=='h')
{
sx2=i;
sy2=j;
}
if (a[i][j]=='S')
{
ex1=i;
ey1=j;
}
if (a[i][j]=='s')
{
ex2=i;
ey2=j;
}
}
}
priority_queue<pair<int,int> > q;
q.push(make_pair(dist(sx1,sy1,sx2,sy2),code(sx1,sy1,sx2,sy2)));
dp[code(sx1,sy1,sx2,sy2)]=dist(sx1,sy1,sx2,sy2);
pre[code(sx1,sy1,sx2,sy2)]=-1;
for (;!q.empty();)
{
int t=q.top().second;
q.pop();
if (visit[t]) continue;
visit[t]=true;
int nowx1,nowx2,nowy1,nowy2;
nowy2=t%35;
t/=35;
nowx2=t%35;
t/=35;
nowy1=t%35;
t/=35;
nowx1=t;
t=code(nowx1,nowy1,nowx2,nowy2);
int i,j;
for (i=0;i<5;i++)
{
int tx1=nowx1+dire[i][0];
int ty1=nowy1+dire[i][1];
if ((tx1<0)||(tx1>=n)||(ty1<0)||(ty1>=n)) continue;
if ((i!=4)&&((nowx1==ex1)&&(nowy1==ey1))) continue;
if ((i==4)&&((nowx1!=ex1)||(nowy1!=ey1))) continue;
if (a[tx1][ty1]=='*') continue;
if (a[tx1][ty1]=='h') continue;
if (a[tx1][ty1]=='s') continue;
for (j=0;j<5;j++)
{
int tx2=nowx2+dire[j][0];
int ty2=nowy2+dire[j][1];
if ((tx2<0)||(tx2>=n)||(ty2<0)||(ty2>=n)) continue;
if ((j!=4)&&((nowx2==ex2)&&(nowy2==ey2))) continue;
if ((j==4)&&((nowx2!=ex2)||(nowy2!=ey2))) continue;
if (a[tx2][ty2]=='*') continue;
if (a[tx2][ty2]=='H') continue;
if (a[tx2][ty2]=='S') continue;
int t2=code(tx1,ty1,tx2,ty2);
if (visit[t2]) continue;
if (dp[t]>dp[t2])
{
dp[t2]=min(dp[t],dist(tx1,ty1,tx2,ty2));
q.push(make_pair(dp[t2],t2));
pre[t2]=t;
}
}
}
}
printf("%.2lf\n",sqrt(dp[code(ex1,ey1,ex2,ey2)]));
dfs1(ex1,ey1,ex2,ey2);
printf("\n");
dfs2(ex1,ey1,ex2,ey2);
printf("\n");
}
return 0;
}
========上午三题=======
========下面是下午=======
题面:http://bailian.openjudge.cn/oitraining2016b/
开场
看到E题唯一一个题
等下冷血竞技场?这不是noijudge上的题么
好像一个map就能水过去
冷静了下,写了一发直接过sample,交
果断9分钟过了
1A!一血!
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<math.h>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
map<int,int> s;
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
scanf("%d",&n);
int i;
s[1000000000]=1;
for (i=0;i<n;i++)
{
int id,ab;
scanf("%d%d",&id,&ab);
printf("%d ",id);
map<int,int>::iterator ii=s.lower_bound(ab);
if (ii==s.begin())
{
printf("%d\n",(*ii).second);
}
else
{
int t1=(*ii).first-ab;
int val1=(*ii).second;
ii--;
int t2=ab-(*ii).first;
int val2=(*ii).second;
if ((t1<t2)||((t1==t2)&&(val1<val2)))
{
printf("%d\n",val1);
}
else
{
printf("%d\n",val2);
}
}
if (s[ab]==0) s[ab]=id;
s[ab]=min(s[ab],id);
}
return 0;
}
然后..我擦?那么多人都过了A?几个意思
感觉难道A题是sb题?为啥都是0Kb/0ms过的
然后..
喜闻乐见的告诉我们A题数据有问题别交
然后他们全部被rejudge成WA/TLE了
我怎么就这么轻易的rank 1了..感觉好慌啊
过了一会儿有人过AE了,我就掉下去了
想吐槽一发
上午我记住密码了一发,之后有人拿我的号交了个E...
然后..
出现了一些奇怪的情况
所以..让我重新交一发
所以就多了一次罚时
然后..掉下去了
感觉F题是个AC自动机的东西
*题意:给你n个字符串,要问你每个字符串是否在大字符串中出现过
*字符串可能被折叠成"[x个T]"的形式
*如果一个字符串出现过,它的子串视为没有出现过
然后..
就写了一发..
一直在RE,终于调到不RE了!
WA了!
思考了一发,重新修改修改
过了..
又是一血..
一血进度5/5..
这题主要是第三个*有点难弄而已..
大概需要在适当的地方(见代码)去稍微去更新下,大概就可以了..
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<math.h>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
char a[5100005];
struct node
{
int flag;
bool vis;
node * fail;
node * ch[26];
};
int top=0;
node * new_node()
{
static node a[3000005];
memset(a[top].ch,0,sizeof(a[top].ch));
a[top].flag=0;
a[top].vis=false;
return &a[top++];
}
void read_str()
{
int now=0;
char x;
for (;;)
{
x=getchar();
if (x=='[')
{
int y;
scanf("%d",&y);
int i=0;
static char z[5100005];
for (;;)
{
z[i]=getchar();
if (z[i]==']') break;
i++;
}
for (;y>0;y--)
{
int j;
for (j=0;j<i;j++)
{
a[now++]=z[j];
}
}
continue;
}
a[now++]=x;
if (x=='\n') return;
if (x==-1)
{
a[now-1]='\n';
return;
}
}
}
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int t;
scanf("%d",&t);
int zu;
for (zu=0;zu<t;zu++)
{
int n;
scanf("%d",&n);
read_str();
int i;
top=0;
node * root=new_node();
for (i=0;i<n;i++)
{
read_str();
int j;
node * now=root;
for (j=0;a[j]!='\n';j++)
{
if (now->ch[a[j]-'A']==0)
{
now->ch[a[j]-'A']=new_node();
}
now=now->ch[a[j]-'A'];
}
now->flag=true;
}
static node * que[3000005];
int front=0,rail=1;
que[0]=root;
root->fail=root;
for (;front<rail;front++)
{
node * t=que[front];
int i;
for (i=0;i<26;i++)
{
if (t->ch[i]==0)
{
t->ch[i]=t->fail->ch[i];
if (t->ch[i]==0) t->ch[i]=root;
}
else
{
t->ch[i]->fail=t->fail->ch[i];
if (t==root) t->ch[i]->fail=root;
que[rail++]=t->ch[i];
}
}
}
read_str();
node * now=root;
for (i=0;a[i]!='\n';i++)
{
now=now->ch[a[i]-'A'];
now->vis=true;
}
for (i=rail-1;i>=0;i--)
{
if (que[i]->vis) que[i]->fail->vis=true;
}
for (i=rail-1;i>=0;i--)
{
int j;
for (j=0;j<26;j++)
{
if (que[i]->ch[j]!=que[i]->fail->ch[j])
{
if (((que[i]->ch[j]->flag)&&(que[i]->ch[j]->vis))||(que[i]->ch[j]->flag==2))
{
que[i]->flag=2;
}
}
}
if (que[i]->flag)
{
if (que[i]->vis)
{
que[i]->fail->flag=2;
}
else if (que[i]->flag==2)
{
que[i]->fail->flag=2;
}
}
}
int sum=0;
for (i=0;i<rail;i++)
{
if ((que[i]->vis)&&(que[i]->flag==1))
{
sum++;
}
}
printf("%d\n",sum);
}
return 0;
}
然后..
接下来就是回头看A题
*题意:给你n个点(n<=50000)求两两的最长欧几里德距离的平方
思考了一发,根据坐标范围在[-10000,10000]内的性质
果断大暴力走起
前面因为某些原因电脑卡了直接交,WA了两次(后来发现sample没过)
又TLE了一次,一怒之下我把n^2的值给预处理了
过了..2960ms/3000ms
这个不是一血..
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<math.h>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int dist(int x,int y,int xx,int yy)
{
return (xx-x)*(xx-x)+(yy-y)*(yy-y);
}
int bi[20005],bx[20005];
int square[20005];
int main()
{
int n;
scanf("%d",&n);
int i;
for (i=0;i<=20000;i++)
{
bi[i]=200000;
bx[i]=-100000;
square[i]=i*i;
}
for (i=0;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
bi[x+10000]=min(bi[x+10000],y);
bx[x+10000]=max(bx[x+10000],y);
}
int max_ans=0;
for (i=0;i<=20000;i++)
{
if (bx[i]==-100000) continue;
int j;
for (j=i;j<=20000;j++)
{
if (bx[j]==-100000) continue;
int ans=square[j-i];
if (bx[j]-bi[i]>bx[i]-bi[j]) ans+=square[bx[j]-bi[i]]; else ans+=square[bx[i]-bi[j]];
if (ans>max_ans) max_ans=ans;
}
}
printf("%d\n",max_ans);
}
然后就来看D
D似乎也不是什么难题..
*题意:
从2000年1月1号0时开始算第一个小时
你要在m个小时内做月饼,第i个小时做的代价是给定的,做一个就要那么大的代价
每个月饼做出来以后,保质期是T天
每个月饼放冰箱里冷场的代价是S,做出来不卖掉就得冷藏
现在有一堆人过来订月饼吃,你要求最小的代价,使得满足所有人的订单
PS:每个小时的整点时刻可以做任意多个月饼
一个线段树题..
我们考虑一发
我们可以发现,每个订单是独立的..
然后..线段树搞下就行了..
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<math.h>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int querys[2505];
int a[100005];
int val[1<<18];
void build_tree(int num,int l,int r)
{
if (l==r-1)
{
val[num]=a[l];
return;
}
int mid=(l+r)/2;
build_tree(num*2+1,l,mid);
build_tree(num*2+2,mid,r);
val[num]=min(val[num*2+1],val[num*2+2]);
}
int query(int num,int l,int r,int l0,int r0)
{
if ((l0<=l)&&(r<=r0))
{
return val[num];
}
int mid=(l+r)/2;
int ans=1999999999;
if (l0<mid) ans=min(ans,query(num*2+1,l,mid,l0,r0));
if (mid<r0) ans=min(ans,query(num*2+2,mid,r,l0,r0));
return ans;
}
int days[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};
map<string,int> ma;
int need[2505];
int read_time(int x)
{
static char a[5];
scanf("%s",a);
string b=a;
int month=ma[b];
int day;
int year;
scanf("%d%d",&day,&year);
year-=2000;
day--;
int hour;
scanf("%d",&hour);
scanf("%d",&need[x]);
for (;;)
{
if (month==0)
{
if (year==0) break;
year--;
month=12;
}
if ((month==2)&&(year%4==0)) day++;
day+=days[month];
month--;
}
return day*24+hour+1;
}
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
//"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov" or "Dec"
ma["Jan"]=0;
ma["Feb"]=1;
ma["Mar"]=2;
ma["Apr"]=3;
ma["May"]=4;
ma["Jun"]=5;
ma["Jul"]=6;
ma["Aug"]=7;
ma["Sep"]=8;
ma["Oct"]=9;
ma["Nov"]=10;
ma["Dec"]=11;
for (;;)
{
int n,m;
scanf("%d%d",&n,&m);
if ((n==0)&&(m==0)) return 0;
int i;
for (i=0;i<n;i++)
{
querys[i]=read_time(i);
}
int s,t;
scanf("%d%d",&t,&s);
for (i=0;i<m;i++)
{
int x;
scanf("%d",&x);
x+=s*(m-i-1);
a[i]=x;
}
build_tree(0,0,m);
long long ans=0;
for (i=0;i<n;i++)
{
ans+=(query(0,0,m,max(querys[i]-t-1,0),querys[i])-s*(m-querys[i]))*(long long)need[i];
}
cout<<ans<<endl;
}
return 0;
}
B题是个计算几何,不会写
C题..不知道怎么弄..
好像是个二分图的最小覆盖?
没时间弄了不太会..不管了
Jun 05, 2016 09:59:58 AM
跪fb爷
Jun 05, 2016 09:55:53 PM
今天还有个fb..