正文
2016-2017 ACM-ICPC Southeastern European Regional Programming Contest (SEERC 2016)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目链接 Codefores_Gym_101164
Solved 6/11
Penalty
Problem A
Problem B
Problem C
Problem D
Problem E
Problem F
预处理出一个pre数组
pre[i]表示i位字母数以内用掉多少个字母
然后就可以算出要计算的位置是第多少个字母数
最后就是转成26进制了
注意是没有0有26的26进制
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
int n;
int siz[],pre[],ans[];
int main()
{
//freopen("F.in","r",stdin);
siz[]=;
siz[]=*+;
siz[]=**+*+;
siz[]=***+**+*+;
siz[]=siz[]+****;
siz[]=siz[]+*****;
pre[]=siz[];
pre[]=pre[]+(siz[]-siz[])*;
pre[]=pre[]+(siz[]-siz[])*;
pre[]=pre[]+(siz[]-siz[])*;
pre[]=pre[]+(siz[]-siz[])*;
pre[]=pre[]+(siz[]-siz[])*;
while (~scanf("%d",&n))
{
n++;
int i;
for (i=;i>=;i--)
if (n>pre[i]) break;
int pos=i;
n=n-pre[pos];
int nxt=n/(pos+);
int rest=n%(pos+);
if (rest!=) nxt++;
else rest=pos+;
n=siz[pos]+nxt;
memset(ans,,sizeof(ans));
int cnt=pos+;
while (cnt--)
{
ans[cnt+]+=n%;
if (ans[cnt+]==)
{
ans[cnt+]=;
ans[cnt]--;
}
n=n/;
}
printf("%c\n",'A'+(ans[rest]-));
}
return ;
}
Problem G
Problem H
可以发现一定可以把所有的点连起来
因此可以不断的建立凸包
然后用一条边把外面的大凸包和里面的小凸包连起来
为了确保连成螺旋形
在建立里面的小凸包时将上一个大凸包最后一个点也加进去
然后依次连接即可
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
#define y1 khjk
#define y2 kjkj
const double pi=acos(-1.0);
struct point
{
double x,y;
int id;
point(){}
point(double _x,double _y):x(_x),y(_y)
{}
point operator -(const point &b) const
{
return point(x-b.x,y-b.y);
}
double operator *(const point &b) const
{
return x*b.x+y*b.y;
}
double operator ^(const point &b) const
{
return x*b.y-y*b.x;
}
bool operator <(const point &b) const
{
return y<b.y||(y==b.y&&x<b.x);
}
};
double cross(point sp,point ep,point op)
{
//cout<< (sp.x-op.x)*(ep.y-op.y)-(sp.y-op.y)*(ep.x-op.x)<<endl;
return (sp.x-op.x)*(ep.y-op.y)-(sp.y-op.y)*(ep.x-op.x);
}
int n,L;
point p[],s[],u[],as[],w[];
int ans[],id[],nid[];
bool used[];
bool cmp(const point &a, const point &b)//逆时针排序
{
point origin=s[];
return cross(a,b,origin)> ;
} int convex(int n)
{
int i, len, top = ;
//cout<<"hhhHH"<<endl;
sort(p+, p + n+);
if(n == ) return ; s[] = p[];
if(n == ) return ; s[] = p[];
if(n == ) return ; s[] = p[]; for(int i = ; i <=n; i++)
{
while(top >&& cross(s[top], s[top - ],p[i])>) top--;
s[++top] = p[i];
//cout<<top<<" "<<id[i]<<endl;
} len = top; s[++top] = p[n - ]; for(int i = n - ; i >= ; i--)
{
while(top!=len && cross(s[top], s[top - ],p[i])>) top--;
s[++top] = p[i];
//cout<<top<<" "<<id[i]<<endl;
}
return top;
}
double dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
int fg=;
while (~scanf("%d",&n))
{
int i;
for (i=;i<=n;i++)
{
double x,y;
scanf("%lf%lf",&x,&y);
p[i]=point(x,y);
p[i].id=i;
w[i]=p[i];
}
int rest=n;
memset(used,false,sizeof(used));
int cnt=convex(n);
cnt--;
int ct=;
//sort(s+2,s+cnt+1,cmp);
for (i=;i<=cnt;i++)
ans[++ct]=s[i].id,used[s[i].id]=true,as[ct]=s[i];
while (cnt<rest)
{
rest=;
u[rest]=as[ct];
//cout<<as[ct].id<<endl;
int id=as[ct].id;
ct--;
for (i=;i<=n;i++)
if (!used[i])
u[++rest]=w[i];
for (i=;i<=rest;i++)
p[i]=u[i];//cout<<p[i].id<<" ";
//cout<<endl;
cnt=convex(rest);
cnt--;
//sort(s+2,s+cnt+1,cmp);
for (i=;i<=cnt;i++)
if (s[i].id==id) break;
//cout<<cnt<<endl;
//for (int j=1;j<=cnt;j++)
// cout<<s[j].id<<" ";
//cout<<endl;
int now=i;
for (i=;i<=cnt;i++)
{
ans[++ct]=s[now].id;
as[ct]=s[now];
used[s[now].id]=true;
now++;
if (now==cnt+) now=;
}
}
printf("%d\n",n);
for (i=;i<n;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[n]);
}
return ;
}
Problem I 打表发现ans <= 9
考虑BFS
不必把所有的状态都存进去
只要存能取的最大数的前面70个即可
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
struct ss
{
int x,fa,y;
};
ss q[];
int h,t,n;
bool b[];
int ans[];
inline bool cmp(int x,int y)
{
return x>y;
}
void push(int x,int y)
{
if (b[x]) return;
b[x]=true;
t++;
q[t].fa=h;
q[t].x=x;
q[t].y=y;
if (x==n)
{
int i=,k=t;
while (k!=)
{
i++;
ans[i]=q[k].y;
k=q[k].fa;
}
printf("%d\n",i-);
sort(ans+,ans+i+,cmp);
int j;
for (j=;j<i-;j++)
printf("%d ",ans[j]);
printf("%d\n",ans[i-]);
exit();
}
}
int main()
{
scanf("%d",&n);
h=;
t=;
q[].fa=;
q[].x=;
q[].y=;
while (h<t)
{
h++;
int x=q[h].x;
int rest=n-x;
int i;
int l=,r=;
while (l<=r)
{
int mid=(l+r)>>;
if (mid*mid*mid>rest)
r=mid-;
else l=mid+;
}
int p=l-;
for (i=p;i>=max(,p-);i--)
push(x+i*i*i,i);
}
return ;
}
Problem J
Problem K
考虑字符串Hash
枚举两个断点，然后分成三段，总共有6个不同的排列。
对于每一段用预处理的Hash,O(1)判断即可。
有解就退出
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) typedef long long LL; const int N = 5010;
const LL mod = 1e9 + 7; LL base = 1e10 + 3;
LL sHash[N], sbin[N];
LL tHash[N], tbin[N];
int n;
char s[N], t[N];
LL cc[N];
int yy[N]; void sHashtable(){
sbin[0] = 1LL;
rep(i, 1, n) sbin[i] = (sbin[i - 1] * base);
rep(i, 1, n) sHash[i] = (sHash[i - 1] * base + s[i]);
} inline LL sgethash(const int &l, const int &r){
return (sHash[r] - sHash[l - 1] * sbin[r - l + 1]);
} void tHashtable(){
tbin[0] = 1LL;
rep(i, 1, n) tbin[i] = (tbin[i - 1] * base);
rep(i, 1, n) tHash[i] = (tHash[i - 1] * base + t[i]);
} inline LL tgethash(const int &l, const int &r){
return (tHash[r] - tHash[l - 1] * tbin[r - l + 1]);
} void print(int l1, int r1, int l2, int r2, int l3, int r3){
puts("YES");
rep(i, l1, r1) putchar(t[i]); putchar(10);
rep(i, l2, r2) putchar(t[i]); putchar(10);
rep(i, l3, r3) putchar(t[i]); putchar(10);
exit(0);
} int main(){ scanf("%s", s + 1);
n = strlen(s + 1); rep(i, 0, n) cc[i] = (LL)rand() * (LL)rand() * (LL)rand(); rep(i, 1, n) if (s[i] < 'a') s[i] = s[i] - 'A' + 'a';
scanf("%s", t + 1);
rep(i, 1, n) if (t[i] < 'a') t[i] = t[i] - 'A' + 'a'; sHashtable();
tHashtable(); rep(i, 1, n - 2){
dec(j, n, i + 2){ int l1 = 1, r1 = i;
int l2 = i + 1, r2 = j - 1;
int l3 = j, r3 = n; int c1 = r1 - l1 + 1;
int c2 = r2 - l2 + 1;
int c3 = r3 - l3 + 1; if (sgethash(1, c1) == tgethash(l1, r1)){
if (sgethash(c1 + 1, c1 + c2) == tgethash(l2, r2)){
if (sgethash(c1 + c2 + 1, n) == tgethash(l3, r3)){
print(l1, r1, l2, r2, l3, r3);
}
}
} swap(l2, l3);
swap(r2, r3);
swap(c2, c3);
if (sgethash(1, c1) == tgethash(l1, r1)){
if (sgethash(c1 + 1, c1 + c2) == tgethash(l2, r2)){
if (sgethash(c1 + c2 + 1, n) == tgethash(l3, r3)){
print(l1, r1, l2, r2, l3, r3);
}
}
} swap(l2, l1);
swap(r2, r1);
swap(c2, c1); if (sgethash(1, c1) == tgethash(l1, r1)){
if (sgethash(c1 + 1, c1 + c2) == tgethash(l2, r2)){
if (sgethash(c1 + c2 + 1, n) == tgethash(l3, r3)){
print(l1, r1, l2, r2, l3, r3);
}
}
} swap(l2, l3);
swap(r2, r3);
swap(c2, c3);
if (sgethash(1, c1) == tgethash(l1, r1)){
if (sgethash(c1 + 1, c1 + c2) == tgethash(l2, r2)){
if (sgethash(c1 + c2 + 1, n) == tgethash(l3, r3)){
print(l1, r1, l2, r2, l3, r3);
}
}
} swap(l2, l1);
swap(r2, r1);
swap(c2, c1); if (sgethash(1, c1) == tgethash(l1, r1)){
if (sgethash(c1 + 1, c1 + c2) == tgethash(l2, r2)){
if (sgethash(c1 + c2 + 1, n) == tgethash(l3, r3)){
print(l1, r1, l2, r2, l3, r3);
}
}
} swap(l2, l3);
swap(r2, r3);
swap(c2, c3);
if (sgethash(1, c1) == tgethash(l1, r1)){
if (sgethash(c1 + 1, c1 + c2) == tgethash(l2, r2)){
if (sgethash(c1 + c2 + 1, n) == tgethash(l3, r3)){
print(l1, r1, l2, r2, l3, r3);
}
}
}
}
} puts("NO");
return 0;
}
