比赛地址
[A]Anagrams
题意
定义x,y是b同构的,当且仅当x,y在b进制下的位数相同(无前导0),而且可以通过交换数字顺序将x变成y.
给出数字b,求出有多少个k满足,当k整除x时,看也整除x在b进制下的所有同构数字.
题解
签到题
代码
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
constexpr int MN(1e6+7);
int main()
{
int n;
scanf("%d", &n);
--n;
std::vector<int> vec;
int sq = sqrt(n) + 2;
for (int i=1; i<sq; ++i)
if (n%i == 0)
vec.emplace_back(i), vec.emplace_back(n/i);
std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
for (auto e : vec)
printf("%d ", e);
return 0;
}
[C]Colder-Hotter
题意
交互题.
在二维平面上有一个终点,现在要通过一系列询问确定这个终点的坐标.每次询问输出一个坐标,当该位置比上一个位置更接近终点时,则输出1;当是第一次询问或者没有上一次更接近时,输出0.询问 次数不能超过500次.在这之前要输出终点的坐标.
题解
二分答案.考虑到询问次数的上界较高,而且单纯判断距离较为复杂,所以每次询问格式为(0,y)或者(x,0).通过两次二分确定横纵坐标即可.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
int main(){
long long int x = 0, y = 1e9;
long long int ansx, ansy;
int a;
while(y > x) {
int k = (x+y)%2;
int mid = (x+y)>>1;
printf("0 %I64d\n", x);
fflush(stdout);
scanf("%d", &a);
printf("0 %I64d\n", y);
fflush(stdout);
scanf("%d", &a);
if (a) x = mid + 1;
else y = mid;
}
ansy = x;
x = 0, y = 1e9;
while(y > x) {
int k = (x+y)%2;
int mid = (x+y)>>1;
printf("%I64d 0\n", x);
fflush(stdout);
scanf("%d", &a);
printf("%I64d 0\n", y);
fflush(stdout);
scanf("%d", &a);
if (a) x = mid + 1;
else y = mid;
}
ansx = x;
printf("A %I64d %I64d", ansx, ansy);
return 0;
}
[D]Delay Time
题意
为测量重力加速度,做了两次实验,已知这两次实验的下落时间和下落高度.但是由于秒表不准,每次测量的时间会和实际时间有一个固定的偏差.求这个偏差是多少.
题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
double h1,h2,t1,t2,x,g,t;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline LL Min(LL a,LL b){return (a<b)?a:b;}
inline LL Max(LL a,LL b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
int main(){
scanf("%lf%lf",&h1,&t1);
scanf("%lf%lf",&h2,&t2);
x=sqrt(h1/h2);
t=(t1-x*t2)/(x-1);
g=2*h1/(t1+t)/(t1+t);
printf("%.10lf\n",-t);
//cout<<t<<endl;
return 0;
}
[G]
题意
在二维平面上分布着一些游客.现在要选定一个位置,让所有的游客都集中到这里.位置的选取是随机的,且只能选取坐标上有游客的位置.游客在向目标移动时,可以沿方格走直线或者走对角线.求选择哪个位置,使得最后一个到达的游客所用时间最长.
题解
可以直接构造曼哈顿距离最小生成树求解.改造一下即可求该题意下的最远点对.
下面的做法是直接暴力求凸包,然后旋转卡壳,求最远两点,直接输出...居然过了...
代码
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define IL
const int maxn = 200000 + 7;
const double sqrt2 = sqrt(2);
const double eps = 1e-8;
const double pi = acos(-1.0);
struct CPoint
{
double x, y;
int id;
} pt[maxn];
template <class T>
IL T min(T x, T y)
{
return x < y ? x : y;
}
template <class T>
IL T max(T x, T y)
{
return x > y ? x : y;
}
IL double sqr(double x)
{
return x * x;
}
IL int dcmp(double x)
{
if (x<-eps) return -1;
else return (x>eps);
}
IL double cross(CPoint p0, CPoint p1, CPoint p2)
{
return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}
IL double dot(CPoint p0, CPoint p1, CPoint p2)
{
return (p1.x - p0.x)*(p2.x - p0.x) + (p1.y - p0.y)*(p2.y - p0.y);
}
IL double dissqr(CPoint p1, CPoint p2)
{
return sqr(p1.x - p2.x) + sqr(p1.y - p2.y);
}
IL double dis(CPoint p1, CPoint p2)
{
double dx = p1.x - p2.x, dy = p1.y - p2.y;
if (dx < 0) dx = -dx;
if (dy < 0) dy = -dy;
return dx < dy ? sqrt2*dx + dy - dx : sqrt2*dy + dx - dy;
// return sqrt(sqr(p1.x - p2.x) + sqr(p1.y - p2.y));
}
IL int PointEqual(const CPoint &p1, const CPoint &p2)
{
return dcmp(p1.x - p2.x) == 0 && dcmp(p1.y - p2.y) == 0;
}
CPoint bp; // for polar sorting
int PolarCmp(const CPoint &p1, const CPoint &p2)
{
int u = dcmp(cross(bp, p1, p2));
return u>0 || (u == 0 && dcmp(dissqr(bp, p1) - dissqr(bp, p2)) <0);
}
void convex(CPoint pin[], int n, CPoint ch[], int &m)
{
int i, j, k, u, v;
memcpy(ch, pin, n * sizeof(CPoint));
for (i = k = 0; i<n; i++)
{
u = dcmp(ch[i].x - ch[k].x);
v = dcmp(ch[i].y - ch[k].y);
if (v<0 || (v == 0 && u<0)) k = i;
}
bp = ch[k];
std::sort(ch, ch + n, PolarCmp);
n = std::unique(ch, ch + n, PointEqual) - ch;
if (n <= 1)
{
m = n;
return;
}
if (dcmp(cross(ch[0], ch[1], ch[n - 1])) == 0)
{
m = 2;
ch[1] = ch[n - 1];
return;
}
ch[n++] = ch[0];
for (i = 1, j = 2; j<n; j++)
{
while (i >0 && dcmp(cross(ch[i - 1], ch[i], ch[j])) <= 0) i--;
ch[++i] = ch[j];
}
m = i;
}
struct Ans
{
int i1, i2;
double d;
Ans(int x, int y, double dd) :
i1(x), i2(y), d(dd)
{
}
bool operator <(const Ans &o) const
{
return d<o.d;
}
bool operator >(const Ans &o) const
{
return d>o.d;
}
};
Ans Diameter(CPoint *p, int n)
{
convex(p, n, p, n);
if (n == 2) return Ans(p[0].id, p[1].id, dis(p[0], p[1]));
int u, nu, v, nv, k;
Ans ret(-1, -1, -1);
p[n] = p[0];
for (u = 0, v = 1; u<n; u = nu)
{
nu = u + 1;
while (1)
{
nv = (v + 1) % n;
k = dcmp((p[nu].x - p[u].x) * (p[nv].y - p[v].y) - (p[nv].x - p[v].x) * (p[nu].y - p[u].y));
if (k <= 0) break;
v = nv;
}
ret = max(ret, Ans(p[u].id, p[v].id, dis(p[u], p[v])));
if (k == 0) ret = max(ret, Ans(p[u].id, p[nv].id, dis(p[u], p[nv])));
}
return ret;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%lf %lf", &pt[i].x, &pt[i].y), pt[i].id = i+1;
Ans ss = Diameter(pt, n);
#ifdef _KEVIN
printf("%d %d %lf", ss.i1, ss.i2, ss.d);
#else
printf("%d %d", ss.i1, ss.i2);
#endif
}
[H]Hashing
题意
给出一个整数序列,每个数不超过255.现在需要从其中选出一个子列,使下面的式子取值最大,并求出最大值.
Hash=\sum_{i=0}^{k}a_{i} \ \ xor \ \ i
题解
很经典的DP问题.
考虑到当选择的子列长度过大时,只有二进制后8位才会对答案造成影响.然后盲猜有下面的结论:序列长度过大时,一定会选择长度接近原序列的子列.于是DP状态就可以进行压缩,不嫩得到以下DP方程:
dp[i][j]=Max(dp[k][j-1]+a[i] \ xor \ (j-1)) \ 0 \leq j \leq 255
前一个极大值可以用另一个数组维护,所以总的时间复杂度为
O(255n)
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define N 100010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i;
int a[N];
LL W[550];
LL dp[N][513];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline LL Max(LL a,LL b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Work2(){
int i=0,j=0,x=0,y=0;
LL Ans=0;
memset(W,-1,sizeof(W));
memset(dp,-1,sizeof(dp));
W[255]=0;
for (i=1;i<=n;i++){
for (j=0;j<=255;j++){
x=j?j-1:255;
if (W[x]<0) continue;
y=i/256;
if (y*256+j>i-1) y--;
dp[i][j]=W[x]+(a[i]^(y*256+j));
Ans=Max(Ans,dp[i][j]);
}
for (j=0;j<=255;j++) W[j]=Max(W[j],dp[i][j]);
}
cout<<Ans<<endl;
}
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%X",&a[i]);
Work();
return 0;
}
[I]Illegal or Not
题意
给定签证的停留天数认证规则,求在一些时间段内是否违反了这一规定.
题解
签到题
代码
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
constexpr int MN(18260);
bool vis[MN];
int main()
{
int n;
scanf("%d", &n);
for (int i=0; i<n; ++i)
{
int l, r;
scanf("%d %d", &l, &r);
for (int t=l; t<=r; ++t)
vis[t] = true;
}
bool ok = true;
for (int l=1; l<=1826; ++l)
{
int cnt = 0;
for (int i=0; i<180; ++i)
cnt += vis[l+i];
if (cnt > 90)
{
ok = false;
break;
}
}
puts( ok ? "Yes" : "No");
return 0;
}
[K]King's Rout
题意
有n个人,从1~n编号,现在需要对这n个人排序,要求是先使1号尽可能靠前,然后是2号,以此类推.此外,有m条限制规则,表述是i号必须在j号前面.求排序方案.
题解
根据限制规则反向连边,然后拓扑排序.排序的时候,优先选取编号大的入队.最后将入队顺序倒叙输出即可.
代码
#include <iostream>
#include <cstdio>
#include <queue>
constexpr int MV(2e5+7);
constexpr int ME(4e5+7);
int ind[MV];
std::vector<int> G[MV];
std::priority_queue<int> q;
int sta[MV], top;
void ts(int V)
{
for (int u=1; u<=V; ++u)
if (!ind[u])
q.push(u);
while (!q.empty())
{
int u = q.top();
q.pop();
sta[top++] = u;
for (auto v: G[u])
if (--ind[v] == 0)
q.push(v);
}
}
int main()
{
int V, E;
scanf("%d %d", &V, &E);
int u, v;
while (E--)
scanf("%d%d", &u, &v), G[v].push_back(u), ++ind[u];
ts(V);
while (top--)
printf("%d ", sta[top]);
return 0;
}
总结&吐槽
这场比赛题目难度中等,思维性较强.一开始K题敲定为拓扑排序,但是拓扑的方式被Hack掉了;中间思路一度被带偏了老远.过了很长一段时间才想出正解.G题没有什么好的方法,抱着试一试的心态敲了一个凸包加旋转卡壳,没想到这数据直接给过了QAQ中间H题的DP一度被我口胡出了正解,可能是写法上的问题,我是对512取的模,目的是压常数.最后发现正解也利用了当初猜的一个结论.
之后的比赛碰见思维题还是要大胆一点,果断猜结论.这场中间基本一直都有人在敲键盘,时间分配还算合理.希望之后不会再出现在大众题上卡顿的情况了.
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: ACM暑期集训第九场
本文地址: ACM暑期集训第九场
