比赛地址
目前还在补题
[A] Rush Hour Puzzle
题意
给出一个6\times 6的棋盘,上面散布着有长度为2或3的一些玩具车.每个车为横向或者纵向放置.游戏规则和华容道比较像,问能否在10步数内将某辆车移出棋盘.
题解
DFS爆搜+玄学剪枝
直接深搜,记录下当前棋盘的状态,和每辆车的车头的坐标,车辆长度,横纵情况.然后根据车辆移动的情况搜就行了.
中间加了一些奇奇怪怪的剪枝,同时用了一个感觉不怎么靠谱的Hash函数来记忆化棋盘,没想到居然过了.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 3000010
#define MOD 32767
#define INF 0x3f3f3f3f
using namespace std;
int i,j,cnt,flag,sum,res,Ans=INF;
int C[10][10],l[15],f[15],s[15];
bool ha[MOD+10];
map <int,int> M;
struct Car{
int x,y,f,l;
};
struct Data{
int h;
short m[7][7];
Car c[15];
}a[N];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL int Hash(int x){
reg int i=0,j=0,H=0,s=0;
for (i=1;i<=6;i++)
for (j=1;j<=6;j++){
s=(i-1)*6+j;
H=(H+s*a[x].m[i][j]*15)%MOD;
}
return H;
}
IL void Ready(){
reg int i=0,j=0,x=0;
for (i=1;i<=6;i++)
for (j=1;j<=6;j++){
a[0].m[i][j]=x=C[i][j];
if (x==C[i][j-1] && x!=C[i][j+1]){
a[0].c[x].f=1; a[0].c[x].x=i; a[0].c[x].y=j;
a[0].c[x].l=2;
if (j>2 && x==C[i][j-2]) a[0].c[x].l++;
}
if (x==C[i+1][j] && x!=C[i-1][j]){
a[0].c[x].f=2; a[0].c[x].x=i; a[0].c[x].y=j;
a[0].c[x].l=2;
if (x==C[i+2][j]) a[0].c[x].l++;
}
}
for (i=1;i<=10;i++)
if (a[0].c[i].x) cnt=i,f[i]=a[0].c[i].f,s[i]=a[0].c[i].l;
for (i=1;i<=cnt;i++)
if (a[0].c[i].f==2)
l[a[0].c[i].y]+=a[0].c[i].l;
for (i=a[0].c[1].y+1;i<=6;i++)
if (l[i]==6) {
puts("-1"); flag=1;
return;
}
if (a[0].c[1].x!=3) {
puts("-1"); flag=1;
return;
}
if (a[0].c[1].f!=1) {
puts("-1"); flag=1;
return;
}
a[0].h=Hash(0);
res=6-a[0].c[1].y;
/* for (i=1;i<=10;i++)
if (a[0].c[i].x)
cout<<i<<" "<<a[0].c[i].x<<" "<<a[0].c[i].y<<" "<<a[0].c[i].l<<endl;
*/
}
IL void Dfs(int p,int step){
if (step<=res && a[p].m[3][a[p].c[1].y+1]!=0){
sum--; return;
}
if (a[p].m[3][6]==1){
sum--;
Ans=Min(Ans,8-step); return;
}
if (Ans<=8-step){
sum--; return;
}
if (!step){
sum--; return;
}
if (ha[a[p].h]>step){
sum--; return;
}
ha[a[p].h]=step;
reg int i=0,x=0,y=0,L=0;
res=6-a[0].c[1].y;
/* for (x=1;x<=6;x++){
for (y=1;y<=6;y++){
printf("%d ",a[p].m[x][y]);
}
putchar(10);
}
putchar(10);*/
for (i=1;i<=cnt;i++){
if (f[i]==1){
x=a[p].c[i].x; y=a[p].c[i].y; L=s[i]-1;
if (y==6 || a[p].m[x][y+1]!=0) goto END;
++sum; a[sum]=a[p];
a[sum].m[x][y-L]=0; a[sum].m[x][y+1]=i;
a[sum].c[i].y++;
a[sum].h=Hash(sum);
Dfs(sum,step-1);
END:
if (y<=L+1 || a[p].m[x][y-(L+1)]!=0) continue;
if (i==1) continue;
++sum; a[sum]=a[p];
a[sum].m[x][y]=0; a[sum].m[x][y-(L+1)]=i;
a[sum].c[i].y--;
a[sum].h=Hash(sum);
Dfs(sum,step-1);
} else {
x=a[p].c[i].x; y=a[p].c[i].y; L=s[i]-1;
if (x+L==6 || a[p].m[x+L+1][y]!=0) goto END2;
++sum; a[sum]=a[p];
a[sum].m[x][y]=0; a[sum].m[x+L+1][y]=i;
a[sum].c[i].x++;
a[sum].h=Hash(sum);
Dfs(sum,step-1);
END2:
if (x==1 || a[p].m[x-1][y]!=0) continue;
++sum; a[sum]=a[p];
a[sum].m[x+L][y]=0; a[sum].m[x-1][y]=i;
a[sum].c[i].x--;
a[sum].h=Hash(sum);
Dfs(sum,step-1);
}
}
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
for (i=1;i<=6;i++)
for (j=1;j<=6;j++)
C[i][j]=read();
Ready();
if (flag) return 0;
Dfs(0,8);
if (Ans==INF) {
cout<<"-1"<<endl;
return 0;
}
Ans+=2;
if (Ans>10){
cout<<"-1"<<endl;
return 0;
}
cout<<Ans<<endl;
return 0;
}
[C] Are They All Integers?
题意&题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i,j,k,x,flag=0;
int a[55];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
for (k=1;k<=n;k++){
if (i==j || j==k || i==k) continue;
x=(a[i]-a[j])/a[k];
if (x*a[k]!=(a[i]-a[j])){
flag=1;
}
}
if (flag==1) puts("no");
else puts("yes");
return 0;
}
[D] Tapioka
题意&题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int s;
string a,b,c,d,e;
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
cin>>a>>b>>c;
d="bubble"; e="tapioka";
if (a==d || a==e) s++;
if (b==d || b==e) s++;
if (c==d || c==e) s++;
if (s==3){
puts("nothing");
return 0;
}
if (a!=d && a!=e) cout<<a<<" ";
if (b!=d && b!=e) cout<<b<<" ";
if (c!=d && c!=e) cout<<c<<" ";
return 0;
}
[E] The League of Sequence Designers
题意
给出一段长度为n的整数序列,1 \leq n <2000.并给出了一段求(r-l+1)\sum_{i=l}^{r}a_{i}的最大值的贪心代码.现在要求构造出一段这样的序列,要求正确的最大值比给出代码求出的最大值恰好大k.输出任意一种方案.
题解
简单构造.
直接构造长度为1999的序列.令序列的第一位为-1,后面全都是非负数.这样贪心找到的子序列长度就是1998,正解找到的子序列长度是1999.设后面这些数的和为x.可以得到如下方程:
1999(x-1)-1998x=k
化简得,x=k+1999
然后把x随便填充到后面的空位中即可.
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int main() {
int T; cin >> T; while(T--) {
long long int k, L;
cin >> k >> L;
if (L >= 2000) {
printf("-1\n");
continue;
}
printf("1999\n");
long long int sum = k + 1999;
int tot = 0;
printf("-1 ");
while(sum) {
if (sum > 1000000) {
printf("1000000 ");
sum -= 1000000;
tot++;
}
else {
printf("%d ", sum);
sum = 0;
tot++;
}
}
for (int i = tot+1; i < 1999; i++) printf("0 ");
printf("\n");
}
return 0;
}
[H] Mining a
题意
给出一个数n.求最大的a,使得存在b,满足\frac{1}{n}=\frac{1}{a \oplus b}+\frac{1}{b}.中间的运算符为异或.
题解
有趣的结论题.b=n+1.然后反解出a就行了.
但是并不会证明
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
LL n,i,x,y;
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL LL read(){
LL p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read();
for (i=1;i<=n;i++){
x=read();
y=x*(x+1);
y^=(x+1);
cout<<y<<endl;
}
return 0;
}
[J] Automatic Control Machine
题意
给出m个集合,每个集合中有一些正整数.现在求它的一个最小的集合子集,使得这些集合的并集中恰好包含了n个数.
题解
二进制暴力枚举,拿Bitset直接通过或运算来计算并集的情况.实际运行的速度快的飞起.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<bitset>
#include<queue>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int T,n,m,i,j,Ans,s;
char c[520];
bitset <500> a[17];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
scanf("%d%d",&n,&m);
a[0].reset(); Ans=INF;
for (i=1;i<=m;i++){
scanf("%s",&c);
a[i].reset();
for (j=0;j<n;j++){
if (c[j]=='1')
a[i][j+1]=1;
}
}
for (i=1;i<(1<<m);i++){
a[0].reset(); s=0;
for (j=0;j<m;j++){
if (i&(1<<j)){
s++; a[0]|=a[j+1];
}
}
if (a[0].count()==n) Ans=Min(Ans,s);
}
if (Ans==INF) puts("-1");
else printf("%d\n",Ans);
}
return 0;
}
[K] Length of Bundle Rope
题意&题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
#define N 1010
using namespace std;
int i,j,k,len,T,n,x,y,Ans;
int s[N];
int f[N][N];
priority_queue <int> Q;
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
n=read();
for (i=1;i<=n;i++) Q.push(-read());
Ans=0;
while (Q.size()>1){
x=Q.top(); Q.pop();
y=Q.top(); Q.pop();
Ans-=x+y;
Q.push((x+y));
}
Q.pop();
printf("%d\n",Ans);
}
return 0;
}
[L] Largest Quadrilateral
题意
给出平面上的一堆点,要求从其中找出四个点,使得这四个点围成的多边形的面积最大.(可能有重合的情况)
题解
旋转卡壳+枚举
构造出凸包后,枚举这个四边形的一条直径,然后类似旋转卡壳那样找面积最大的情况.需要卡一下常数.
代码
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define _BS 1048576
char _bf[_BS];
char *__p1=_bf,*__p2=_bf;
#define _IO char *_p1=__p1,*_p2=__p2;
#define _OI __p1=_p1,__p2=_p2;
#define GC (_p1==_p2&&(_p2=(_p1=_bf)+fread(_bf,1,_BS,stdin),_p1==_p2)?EOF:*_p1++)
#define PC putchar
#define _Q_(x) {register char _c=GC,_v=1;for(x=0;_c<48||_c>57;_c=GC)if(_c==45)_v=-1;
#define _H_(x) for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=GC);if(_v==-1)x=-x;}
#define sc(x) _Q_(x)_H_(x)
#define se(x) _Q_(x)else if(_c==EOF)return 0;_H_(x)
#define _G1(_1) int _1;sc(_1)
#define _G2(_1,_2) int _1,_2;sc(_1)sc(_2)
#define _G3(_1,_2,_3) int _1,_2,_3;sc(_1)sc(_2)sc(_3)
#define _gG(_1,_2,_3,_get, ...) _get
#define get(...) _gG(__VA_ARGS__,_G3,_G2,_G1, ...)(__VA_ARGS__)
#define F(i,l,r) for(int i=(l);i<(r);++i)
#define FD(i,l,r) for(int i=(l);i<=(r);++i)
#define IL inline
#define OP operator
#define CON constexpr
using vint = long long;
vint VINF = 0x3f3f3f3f3f3f3f3fLL;
using namespace std;
IL vint sqr(vint x) { return x * x; };
struct Po
{
int id;
vint x, y;
Po() {}
Po(vint x, vint y) : x(x), y(y) {}
Po OP + (const Po &o) const { return Po(x + o.x, y + o.y); }
Po OP - (const Po &o) const { return Po(x - o.x, y - o.y); }
bool OP < (const Po &o) const { return x < o.x || x == o.x && y < o.y; }
bool OP == (const Po &o) const { return x == o.x && y == o.y; }
vint OP ^ (const Po &o) const { return x * o.y - y * o.x; }
vint OP | (const Po &o) const { return sqrt(sqr(x - o.x) + sqr(y - o.y)); }
};
CON int MP = 1e4 + 7;
struct Poly
{
int n;
Po p[MP];
int top;
Po sta[MP];
Poly() : n(0) {}
void clear() { p[n] = sta[top] = {0, 0}, n = 0; top = 0; }
void emplace(const Po &ne) { p[n++] = ne; }
void convex()
{
sort(p, p + n);
top = 0;
for (int i = 0; i < n; ++i)
{
while (top > 1 && ((sta[top - 1] - sta[top - 2]) ^ (p[i] - sta[top - 2])) <= 0)
--top;
sta[top++] = p[i];
}
int k = top;
for (int i = n - 2; i >= 0; --i)
{
while (top > k && ((sta[top - 1] - sta[top - 2]) ^ (p[i] - sta[top - 2])) <= 0)
--top;
sta[top++] = p[i];
}
if (n > 1)
--top;
}
#define MOD(a, b) (a=(a>=b ? a-b:a))
vint rt_cp()
{
this->convex();
if (top <= 2)
return 0;
if (top == 3) // 凹多边形
{
vint ans = 0;
vint min_tri = VINF;
ans = abs((sta[0] - sta[2]) ^ (sta[1] - sta[2]));
for (int i = 0; i < n; i++)
{
if (sta[0].id == p[i].id || sta[1].id == p[i].id || sta[2].id == p[i].id)
continue;
min_tri = min(min_tri, abs((sta[0] - p[i]) ^ (sta[1] - p[i])));
min_tri = min(min_tri, abs((sta[1] - p[i]) ^ (sta[2] - p[i])));
min_tri = min(min_tri, abs((sta[2] - p[i]) ^ (sta[0] - p[i])));
}
if (min_tri == VINF)
return 0;
return ans - min_tri;
}
vint ans = 0;
for (int i = 0; i < top; i++)
{
int ni = i+1, nj = i+2;
MOD(ni, top), MOD(nj, top);
for (int j=nj; j!=i; ++j, MOD(j, top))
{
while (MOD(ni, top) != j && abs((sta[j]-sta[i]) ^ (sta[ni]-sta[i])) - abs((sta[j]-sta[i]) ^ (sta[ni+1]-sta[i])) < 0 ) ++ni;
while (MOD(nj, top) != i && abs((sta[j]-sta[i]) ^ (sta[nj]-sta[i])) - abs((sta[j]-sta[i]) ^ (sta[nj+1]-sta[i])) < 0 ) ++nj;
ans = max(ans, abs((sta[ni] - sta[i]) ^ (sta[j] - sta[i])) + abs((sta[nj] - sta[i]) ^ (sta[j] - sta[i])));
}
}
return ans;
}
} p;
int main()
{
_IO
get(T)
const char *ss[] = {"%lld\n", "%lld.5\n"};
Po x;
while (T--)
{
p.clear();
get(n)
for (int i=0; i<n; ++i)
{
x.id = i;
sc(x.x)sc(x.y)
p.emplace(x);
}
vint ans = p.rt_cp();
printf(ss[ans & 1], ans >> 1);
}
return 0;
}
总结
整场比赛发挥还可以,智商基本上持续在线.比如H题直接猜出了结论节省了很多时间.当然中间还是犯了一些错误,M题开场读完后以为是一个广义Lucas定理,甩给队友持续研究了半天.到最后快结束的时候才发现题目中的取模是重新定义过的,并不是板子题.导致前期开题时人手有些不够,切签到题的速度有些慢.中间推E题构造式子的时候也有些慢.A题在RE了一发之后,一直以为是递归崩栈了,改了几次无果之后才发现是数组越界,多吃了很多次罚时.最后的时间全部用来推F题,感觉是一个SPFA实数费用流模型,但是直到最后也没有完成对模型的修正,正好回头找一队问一下做法.
别人的520用来秀恩爱,我的520用来训练,我们都度过了充实的一天
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2019 ICPC Taipei-Hsinchu Regional Contest 部分题解
本文地址: 2019 ICPC Taipei-Hsinchu Regional Contest 部分题解
