比赛地址
[D]Dream Team
题意
给定一个图，每一个点有点权。求边权和最大的生成树。边权的定义为两点点权的gcd值。
题解
校赛原题，具体题解见这里
话说比赛的时候直接抄校赛的代码，结果直接WA。Debug后发现校赛代码少考虑了所有点的边权全都不为1的情况，这样会少算一些答案。。。校赛数据坑死人
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 200010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,p,i,g,T,q,flag,x;
LL Ans;
int v[N],f[N];
inline int Max(int a,int b){return (a>b)?a:b;}
inline int Find(int x){
return (x==f[x])?x:f[x]=Find(f[x]);
}
int main(){
scanf("%d",&T);
for (g=1;g<=T;g++){
memset(v,0,sizeof(v)); memset(f,0,sizeof(f));
m=0; Ans=0;
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%d",&p);
if (p==1) {Ans++; continue;}
if (v[p]) {Ans+=p; continue;}
v[p]=1; f[p]=p; m=Max(m,p);
}
f[1]=1; v[1]=1;
for (i=(m/2)+1;i;i--){
x=i; p=0; q=0; flag=0;
while (x<=m){
if (!v[x]) goto END;
q=Find(f[x]);
if (flag==0){
flag=q; p=x;
} else {
if (flag==q) goto END;
f[q]=flag; Ans+=(LL)i;
}
END:
x+=i;
}
}
Ans--;
printf("Case %d: %I64d\n",g,Ans);
}
return 0;
}
[E]Evaluations
题意
给定一棵树，树上两点的距离定义为两点路径上所有边的边权之积。求有多少个无序点对(u,v)，使得其距离可以分解为两个质数之积。
题解
首先把边权为1的边缩到一起，这一过程拿并查集维护。然后考虑答案的形式，要么是相邻两点，其边权正好符合题意；要么是存在相邻两条边的边权恰好为两个不同的质数。分别统计这两种答案即可。计算答案的时候，要按照缩点后的点的大小计算方案数。
计算第二种情况时，有两种思路，一种是枚举每一条边，然后枚举两个端点向外延伸出的所有边，检查是否符合题意。每条边被检查的次数和两个端点的度数相关，所以这种算法的时间复杂度是
O(n)
还有一种思路是枚举点，然后遍历延伸出的所有边，统计有多少质数边，和每种质数边有多少。每遇到一条质数边，统计一次答案即可。时间复杂度也是
O(n)
但是，实际提交的时候，第一种思路被卡常了QAQ所以赛后使用的第二种思路AC了这道题。
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define N 200020
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int T,g,i,j,x,y,n,lsum=1,c,flag,Lsum=1;
int head[N],p[N],sum[N],vv[N],Head[N],fa[N];
LL Ans,size[N],cnt[N];
LL ss[N];
struct Data{
int t,l;
};
struct Edge{
int s,t,l,next;
}e[N*8],E[N*8];
vector <int> P[N],pri[N];
inline void Add(int s,int t,int l){
e[lsum].s=s; e[lsum].t=t; e[lsum].l=l; e[lsum].next=head[s]; head[s]=lsum++;
}
inline void Add2(int s,int t,int l){
E[Lsum].s=s; E[Lsum].t=t; E[Lsum].l=l; E[Lsum].next=Head[s]; Head[s]=Lsum++;
}
char buf[1<<15],*fs,*ft;
inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int gint(){
int x=0,ch=gc();
while(ch<'0'||ch>'9') ch=gc();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=gc();
return x;
}
inline int Find(int x){return (x==fa[x])?x:fa[x]=Find(fa[x]);}
inline void Pre(){
int i=0,x=0,y=0;
for (i=2;i<=N-10;i++){
if (vv[i]) continue;
p[++p[0]]=i;
for (x=i*2;x<=100000;x+=i) pri[x].push_back(i),vv[x]=1;
}
for (i=6;i<=N-10;i++){
if (pri[i].size()!=2) continue;
x=pri[i][0]; y=pri[i][1];
if (x*y==i) sum[i]=1;
}
}
inline void Ready(){
int i=0,j=0,x=0,y=0;
for (i=1;i<=n;i++) size[Find(i)]++;
for (i=1;i<=n;i++){
x=Find(i);
for (j=Head[i];j;j=E[j].next){
y=Find(E[j].t);
if (x==y) continue;
if (!vv[E[j].l]) Add(x,y,E[j].l);
else if (sum[E[j].l]) Ans+=size[x]*size[y];
}
}
Ans/=2;
}
inline void Work(){
int i=0,j=0,x=0,y=0,r=0,u=0,k=0;
LL sum=0;
for (i=1;i<=n;i++){
sum=0;
for (j=head[i];j;j=e[j].next){
x=e[j].t; y=e[j].l;
sum+=size[x]; cnt[y]+=size[x];
Ans+=(sum-cnt[y])*size[x];
}
for (j=head[i];j;j=e[j].next) cnt[e[j].l]-=size[e[j].t];
}
}
int main(){
Pre();
T=gint();
for (g=1;g<=T;g++){
n=gint();
memset(size,0,sizeof(size));
memset(e,0,sizeof(e)); memset(head,0,sizeof(head));
memset(E,0,sizeof(E)); memset(Head,0,sizeof(Head));
memset(size,0,sizeof(size));
lsum=1; Ans=0; Lsum=1;
for (i=1;i<n;i++){
x=gint(); y=gint(); c=gint();
fa[i]=i; fa[i+1]=i+1;
if (vv[c]&&c!=1&&!sum[c]) continue;
Add2(x,y,c); Add2(y,x,c);
}
for (i=1;i<=n;i++)
for (j=Head[i];j;j=E[j].next)
if (E[j].l==1) {
x=Find(i); y=Find(E[j].t);
if (x!=y) fa[x]=y;
}
Ready(); Work();
printf("Case %d: %I64d\n",g,Ans);
}
return 0;
}
[F]Forgot the Flag!
题意
给定一个凸多边形，然后每次询问会给出两个多边形内的点的坐标，求从第一个点到边界，再到第二个点的最小距离，以及选取的边界的点的坐标。
题解
根据中学知识，以每条边为镜面，第二个点对称出去，然后计算和第一个点的距离即可。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cctype>
#include <cmath>
#define IL inline
#define LL long long
#define ULL unsigned LL
#define GC getchar()
#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)
template<class T>
void UPRT(const T _){if(_>=10)UPRT(_/10);PC(_%10+48);}
#define UPL(_) UPRT(_),PC(10)
template<class T>
void PRT(const T _){if(_<0){PC(45),UPRT<ULL>(-(ULL)_);return;}if(_>=10)PRT(_/10);PC(_%10+48);}
#define PL(_) PRT(_),PC(10)
constexpr int MN(1e5+7);
const double EPS = 1e-6;
IL double ABS(double x) {return x>0 ? (x>EPS ? x:0) : (x<-EPS ? -x:0);}
IL double MIN(double a, double b) {return a<b ? a:b;}
IL double MAX(double a, double b) {return a>b ? a:b;}
IL bool eq(double a, double b) {return a>b ? a-b<EPS : b-a<EPS;}
IL bool zero(double x) {return x>0 ? x<EPS : x>-EPS;}
IL int sign(double x) {return x>0 ? (x>EPS ? 1:0) : (x<-EPS ? -1:0);}
IL double norm(double x) {return x>0 ? (x>EPS ? x+EPS:0) : (x<-EPS ? x-EPS:0);}
void PRT(const char *fmt, double x)
{
static char buf[666];
sprintf(buf, fmt, norm(x));
bool all_0 = true;
for (char *p=buf; *p; ++p)
if (isdigit(*p) && *p!='0')
{
all_0 = false;
break;
}
printf("%s", buf + (all_0 && *buf=='-'));
}
#define sqr(x) ((x)*(x))
#define cub(x) ((x)*(x)*(x))
struct Po
{
double x;
double y;
Po (void) { }
Po (double xx, double yy) : x(xx), y(yy) {
}
void norm()
{
double d = sqrt(x*x + y*y);
x /= d, y /= d;
}
double operator *(const Po &o) const {return x*o.x + y*o.y;}
double operator ^(const Po &o) const {return x*o.y - y*o.x;}
Po operator +(double d) const {return Po(x+d, y+d);}
Po operator -(double d) const {return Po(x-d, y-d);}
Po operator *(double d) const {return Po(x*d, y*d);}
Po operator /(double d) const {return Po(x/d, y/d);}
Po operator +(const Po &o) const {return Po(x+o.x, y+o.y);}
Po operator -(const Po &o) const {return Po(x-o.x, y-o.y);}
double operator |(const Po &o) const {return sqrt(sqr(x-o.x)+ sqr(y-o.y));}
} po[MN];
struct Li
{
Po s, t;
Li(void) {}
Li(const Po &a, const Po &b) : s(a), t(b) { }
Po get_v_dir()
{
Po d = t - s;
return Po(d.y, -d.x);
}
double dist(const Po &p) const
{
return ABS((t-s) ^ (p-s) / (s | t));
}
Po operator &(const Li &o) const
{
const double p1 = (o.t-o.s) ^ (s-o.s);
const double p2 = (o.t-o.s) ^ (t-o.s);
return Po((s.x*p2 - t.x*p1)/(p2-p1), (s.y*p2 - t.y*p1)/(p2-p1));
}
};
struct Ans
{
double len;
Po c;
};
int main()
{
int T;
sc(T)
Po p1, p2, v, mid, mirror;
Li l;
Ans ans, cans;
for (int cas=1; cas<=T; ++cas)
{
printf("Case %d:\n", cas);
get(n)
F(i, 0, n)
scanf("%lf %lf", &po[i].x, &po[i].y);
get(q)
while (q--)
{
scanf("%lf %lf %lf %lf", &p1.x, &p1.y, &p2.x, &p2.y);
po[n] = po[0];
ans.len = 1e15;
for (int i=0; i<n; ++i)
{
l.s = po[i], l.t = po[i+1];
v = l.get_v_dir();
v.norm();
v = v * l.dist(p1);
mirror = p1 + v + v;
if (sign((l.s-p1) ^ (l.t-p1)) == sign((l.s-mirror) ^ (l.t-mirror)))
{
mid = p1 - v;
mirror = mid - v;
}
cans.len = p2 | mirror;
cans.c = Li(mirror, p2) & l;
if (cans.len < ans.len)
ans = cans;
}
// PRT("%.7f ", ans.len);
// PRT("%.7f ", ans.c.x);
// PRT("%.7f\n", ans.c.y);
printf("%.7f %.7f %.7f\n", ans.len, ans.c.x, ans.c.y);
}
}
return 0;
}
[G]Glorious Stadium
题意
给出两个整数k和n。每一次画出一个正k边形，然后画出其内接圆，要求该内接圆是上一个正多边形的外接圆。并给出第一个内接圆的半径R。每一个正多边形的面积减去其内接圆的面积。求所有有效面积之和。
题解
签到题
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
double mi(double a, int n) {
if (n == 0) return 1;
if (n == 1) return a;
double m = mi(a, n/2);
m = m * m;
if (n%2) m = m * a;
return m;
}
double nei1, nei2, bili1, bili2, s1, s2, K, duibian, s, sk;
int T, n, r, k;
int main() {
double pi = acos(-1);
cin >> T;
for (int t = 1; t <= T; t++) {
scanf("%d%d%d", &n, &r, &k);
nei1 = pi/k;
bili1 = cos(nei1);
K = 1.0/bili1/bili1;
duibian = tan(nei1);
s1 = duibian/2;
s2 = nei1/2;
bili2 = (s1-s2)/s2;
sk = pi * r * r;
if (n == 1) s = sk;
else s = (mi(K, n) - 1)/(K-1) * sk;
printf("Case %d: %.5lf\n", t, s*bili2);
}
return 0;
}
[H]Half Nice Years
题意
给定一个范围[L,R]，求该范围内的最大十进制整数，使得该整数从正中间 分为两部分后(长度若为奇数则分为k和k+1两部分)，两段的gcd大于1。
题解
略
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int p[1000005];
int anss[10005], pan[10005];
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a%b);
}
int s[15];
bool ok(int n) {
int k = n;
int wei = 0;
while(k) { s[++wei] = k%10; k /= 10; }
int a = 0, b = 0;
if (wei % 2 == 0) {
for (int i = wei; i > wei/2; i--) a = a*10 + s[i];
for (int i = wei/2; i >= 1; i--) b = b*10 + s[i];
} else {
for (int i = wei; i > wei/2+1; i--) a = a*10 + s[i];
for (int i = wei/2+1; i >= 1; i--) b = b*10 + s[i];
}
if (a == 0 || b == 0) return false;
if (gcd(a, b) > 1) return true;
return false;
}
void st() {
p[1] = 1;
for (int i = 2; i <= 1000000; i++) {
if (p[i] == 0)
for (int j = i; j <= 1000000/i; j++) if (p[i*j] == 0) p[i*j] = i;
}
for (int i = 10; i <= 10000; i++) if (ok(i)) pan[i] = 1;
int now = 0;
for (int i = 10; i <= 10000; i++) {
if (pan[i]) now = i;
anss[i] = now;
}
}
long long int max(long long int a, long long int b) {
if (a > b) return a;
return b;
}
long long int find(long long int n) {
if (n <= 10000) return 1LL * anss[n];
long long int k = n, ans = 0;
int wei = 0;
while(k) { s[++wei] = k%10; k /= 10; }
int a = 0, b = 0, bili = 1, A;
if (wei % 2 == 0) {
for (int i = wei; i > wei/2; i--) a = a*10 + s[i];
for (int i = wei/2; i >= 1; i--) b = b*10 + s[i];
for (int i = wei/2; i >= 1; i--) bili *= 10;
} else {
for (int i = wei; i > wei/2+1; i--) a = a*10 + s[i];
for (int i = wei/2+1; i >= 1; i--) b = b*10 + s[i];
for (int i = wei/2+1; i >= 1; i--) bili *= 10;
}
A = a;
while(A > 1) {
int c = p[A];
if (c == 0) c = A;
if (b - b%c > 0) ans = max(ans, 1LL*a*bili+b-b%c);
A /= c;
}
A = a-1; b = bili - 1;
while(A > 1) {
int c = p[A];
if (c == 0) c = A;
if (b - b%c > 0) ans = max(ans, 1LL*(a-1)*bili+b-b%c);
A /= c;
}
return ans;
}
int T;
long long int ans, a, b;
int main() {
st();
cin >> T;
for (int t = 1; t <= T; t++) {
int flag = 1;
scanf("%I64d%I64d", &a, &b);
if (b <= 21) flag = 0;
if (flag) ans = find(b);
if (flag && ans == 0 && b > a) ans = find(b-1);
if (ans < a) flag = 0;
if (flag) printf("Case %d: %I64d\n", t, ans);
else printf("Case %d: impossible\n", t, ans);
}
return 0;
}
[J]Jacked Tickets
题意
给定两个整数n和m，现需要把整数n分为m份，所有份总和为n。大小为k的份数有一个损失P(k),P(k)是凹函数。求最小损失。
题解
签到题
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int n, a, b, T;
long long int p[505];
int main() {
cin >> T;
for (int t = 1; t <= T; t++) {
printf("Case %d:\n", t);
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%I64d", &p[i]);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &a, &b);
if (b > a) printf("impossible\n");
else {
long long int ans = 0;
int k = a/b;
int s = a%b;
for (int i = 1; i <= s; i++) ans += p[k+1];
for (int i = s+1; i <= b; i++) ans += p[k];
printf("%I64d\n", ans);
}
}
}
return 0;
}
[K]Katryoshka
题意
给定三种组件A,B,C。有三种商品，每制造一件商品，消耗的组件数量分别是(2,0,1),(2,1,1),(1,1,1).求最多能造多少商品。
题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define l(x) x<<1
#define r(x) (x<<1)+1
#define LL long long
using namespace std;
int n,m,k,i,T,s1,s2;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int 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("%d",&T);
for (i=1;i<=T;i++){
scanf("%d%d%d",&n,&m,&k);
s1=s2=0;
if (m>=n) s1=n; else s1=m+(n-m)/2;
s2=n/2; if ((n%2)&&m) s2++;
printf("Case %d: %d\n",i,Min(Max(s1,s2),k));
}
return 0;
}
[L]Lazy ERCD
题意
有n支队伍参加比赛，每进行一轮比赛会淘汰一支队伍，求需要几场比赛能确定冠军队伍。
题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int T,n,i;
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 int Max(int a,int 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("%d",&T);
for (i=1;i<=T;i++){
scanf("%d",&n);
printf("Case %d: %d\n",i,n-1);
}
return 0;
}
总结&吐槽
这场比赛算是最近几场里面稍微简单一些的了，以中低档题为主。E题在比赛中一直被卡常，I题写的二维莫队也被卡常了(正解CDQ分治)。如果能够做出来就是9题了QAQ。话说第一次见这么丧心病狂的套题，非要卡常，输出还必须格式化
目前训练已经进行了四场了，目前的积分在第九名，差一点可以进队。希望接下来可以好好发挥。
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: ACM暑期集训第四场
本文地址: ACM暑期集训第四场
