比赛地址
[A]Alarm Clock
题意
给定一个数字时钟的显示方式，然后给出显示屏上高亮的短横的总数，求可能的时间是多少。
题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
int ans[100];
int pan(int a) {
if (a == 0) return 6;
if (a == 1) return 2;
if (a == 2) return 5;
if (a == 3) return 5;
if (a == 4) return 4;
if (a == 5) return 5;
if (a == 6) return 6;
if (a == 7) return 3;
if (a == 8) return 7;
if (a == 9) return 6;
return 1;
}
int main(){
freopen("alarm.in", "r", stdin);
freopen("alarm.out", "w", stdout);
int nowans, n;
memset(ans, -1, sizeof(ans));
for (int i = 0; i < 24; i++) {
for (int j = 0; j < 60; j++) {
nowans = 0;
nowans += pan(i%10);
nowans += pan(i/10);
nowans += pan(j%10);
nowans += pan(j/10);
ans[nowans] = i*100+j;
}
}
scanf("%d", &n);
if (ans[n] == -1) {
printf("Impossible");
return 0;
}
printf("%02d:%02d", ans[n]/100, ans[n]%100);
return 0;
}
[B]Buffcraft
题意
给出一个角色的初始生命，以及所能携带的道具总数。有两种道具，一种是直接增加生命上限的，另一种是按百分比增加生命上限。然后每种道具各有一定的数量。每个道具都有一个参数，表示其作用的效果是多少。求怎样携带道具，可以使生命上限最高。
题解
和校赛个人综合赛的一道题特别像。原题找不到了QAQ回头再补
贪心。
首先对两种道具按照作用效果从大到小排序，然后枚举道具总数的分配方式即可。
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#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,k,b,c1,c2,i;
struct Data{
LL x,id;
}a[N],p[N];
inline bool cmp(Data x,Data y){return x.x>y.x;}
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 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 Work(){
int i=0,j=0,Ans=0;
LL s=0,S=100;
double ss=0,SS=0,cnt=0;
int head=0,tail=Min(c2,k);
for (i=1;i<=Min(c2,k);i++) S+=p[i].x;
if (S>0) SS=log(S); else SS=-10000000;
s=b;
if (k>c2)
for (i=1;i<=k-c2;i++) s+=a[i].x,head=i;
head++;
if (s>0) ss=log(s); else ss=-10000000;
cnt=ss+SS; Ans=head-1;
for (i=1;i<=k;i++){
S-=p[tail--].x; s+=a[head++].x;
if (S>0) SS=log(S); else SS=-10000000;
if (s>0) ss=log(s); else ss=-10000000;
if (ss+SS>cnt){
cnt=ss+SS; Ans=head-1;
}
if (head>c1||tail<=0) break;
}
cout<<Ans<<" "<<Min(c2,k-Ans)<<endl;
for (i=1;i<=Ans;i++) printf("%d ",a[i].id);
if (Ans) cout<<endl;
for (i=1;i<=Min(c2,k-Ans);i++) printf("%d ",p[i].id);
}
int main(){
freopen("buffcraft.in","r",stdin);
freopen("buffcraft.out","w",stdout);
scanf("%d%d%d%d",&b,&k,&c1,&c2);
if (c1+c2<=k){
cout<<c1<<" "<<c2<<endl;
for (i=1;i<=c1;i++) printf("%d ",i);
if (c1) cout<<endl;
for (i=1;i<=c2;i++) printf("%d ",i);
return 0;
}
for (i=1;i<=c1;i++) scanf("%d",&a[i].x),a[i].id=i;
for (i=1;i<=c2;i++) scanf("%d",&p[i].x),p[i].id=i;
sort(a+1,a+1+c1,cmp); sort(p+1,p+1+c2,cmp);
Work();
return 0;
}
[D]Digits
题意
给出一个数n，求n个数字的和，要求是这n个数的各位数字之和必须相等，且总和最小。
题解
签到题
代码
#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;
int n,i,j;
LL Ans,cnt;
vector <int> v[1100];
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;
}
inline void Ready(){
int i=0,x=0,sum=0;
for (i=1;i<=10000000;i++){
x=i; sum=0;
while (x){
sum+=x%10; x/=10;
}
v[sum].push_back(i);
}
}
int main(){
freopen("digits.in","r",stdin);
freopen("digits.out","w",stdout);
scanf("%d",&n);
Ready();
Ans=(LL)1000000000000;
for (i=1;i<=1000;i++){
cnt=0;
if (v[i].size()<n) continue;
for (j=1;j<=n;j++) cnt+=(LL)v[i][j-1];
if (cnt<Ans) {
Ans=cnt;
}
}
cout<<Ans<<endl;
return 0;
}
[G]Grave
题意
给出两个矩形的坐标，两个矩形是包含的关系。再给出另一个矩形的长宽信息，问能否把这个矩形塞到大矩形里面而且和这两个矩形不相交。
题解
签到题
代码
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstdint>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#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(1e6+7);
int main()
{
freopen("grave.in", "r", stdin);
freopen("grave.out", "w", stdout);
LL bx1, bx2, by1, by2;
LL sx1, sx2, sy1, sy2;
LL w, h;
sc(bx1)sc(by1)
sc(bx2)sc(by2)
sc(sx1)sc(sy1)
sc(sx2)sc(sy2)
sc(w)sc(h)
bool ok = false;
LL ww = bx2-bx1, hh = by2-sy2;
ok |= (ww >= w && hh >= h);
ww = sx1-bx1, hh = by2-by1;
ok |= (ww >= w && hh >= h);
ww = bx2-bx1, hh = sy1-by1;
ok |= (ww >= w && hh >= h);
ww = bx2-sx2, hh = by2-by1;
ok |= (ww >= w && hh >= h);
puts(ok ? "Yes" : "No");
return 0;
}
[I]Instruction
题意
给出一个铁路网的部署情况，铁路网由两种部件构成，一种是岔道，岔道有一种输入轨道和两种输出轨道模式，输入和输出都可以是另外一个岔道。一开始，岔道的输出轨道模式自动调节成连接编号更小的下一个部件。一种是终点站台，站台只有一种输入轨道，表示其连接向一个岔道的输出。然后给出m列火车的发车信息，这些火车会从起点出发，驶向终点站台。求修改岔道的方案，使得火车都可以驶向终点。
题解
大模拟。预处理出铁路网(其实是铁路树),然后按时间模拟每个火车的行驶情况。需要改变岔道就记录下来即可。
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 10010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,sw,pl,i,x,m,y,j;
int fa[N],k[N],id[N],X[N],rr[N],rrr[N];
int head[N],w[N];
int t[100010];
char c[110][110],cc[110][110],ss[110];
struct Data{
int t,x;
};
vector <int> son[N],z[N],re;
vector <Data> Ans;
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 int Max(int a,int b){return (a>b)?a:b;}
inline LL read(){
LL 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 Ready(int x){
int i=0,y=0,p=0,yy=0,pp=0;
if (!son[x].size()) return;
if (!x){
Ready(son[x][0]);
return;
}
k[x]=Min(son[x][0],son[x][1]);
Ready(son[x][0]); Ready(son[x][1]);
}
inline void Find(int x){
re.push_back(x);
if (!x) return;
Find(fa[x]);
}
inline void Work(){
int i=0,x=0,to=0,no=0;
re.clear();
for (i=0;i<=20000;i++){
for (j=0;j<re.size();j++){
x=re[j];
if (!x) continue;
no=w[x]; to=z[x][++head[x]];
if (k[no]!=to) {
k[no]=to; Ans.push_back((Data){i,no});
}
w[x]=to;
if (head[x]>=z[x].size()-1) re[j]=0;
}
if (t[i]) re.push_back(t[i]),w[t[i]]=z[t[i]][1],head[t[i]]=1;
}
}
int main(){
freopen("instruction.in","r",stdin);
freopen("instruction.out","w",stdout);
scanf("%d",&n);
sw=0; pl=0;
for (i=1;i<=n;i++){
scanf("%s",&c[i]);
if (c[i][0]=='s') {
scanf("%d",&X[i]);
} else {
scanf("%d%s",&X[i],&cc[i]);
}
}
for (i=1;i<=n;i++){
if (c[i][0]=='s') {
fa[i]=X[i]; son[X[i]].push_back(i);
} else {
fa[i]=X[i]; son[X[i]].push_back(i);
id[cc[i][0]-'a'+1]=i;
}
}
Ready(0);
scanf("%d",&m);
for (i=1;i<=m;i++){
scanf("%d%s",&x,&ss);
y=id[ss[0]-'a'+1];
re.clear();
Find(y);
for (j=re.size()-1;j>=0;j--) z[i].push_back(re[j]);
t[x]=i;
}
Work();
cout<<Ans.size()<<endl;
for (i=0;i<Ans.size();i++)
printf("%d %d\n",Ans[i].x,Ans[i].t);
return 0;
}
[J]Joy of Flight
题意
给出二维平面上飞机的起点坐标和终点坐标，以及速度的控制范围。然后已知每一秒的风向信息(由一个平面向量表示)。飞机的行驶方向便是速度向量和风向向量的合成。求飞机飞向终点的速度调整方案。
题解
签到题
代码
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#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)
inline double dist(double x1, double y1, double x2, double y2)
{
return sqrt((x1-x2) * (x1-x2) + (y1-y2) * (y1-y2));
}
constexpr int MN(1e5+7);
double sx, sy, fx, fy;
int n, k, t[MN];
double max_v, wx[MN], wy[MN];
double get_dist(int ct)
{
int cur = 0;
double vx = 0, vy = 0;
double cur_x = fx, cur_y = fy;
F(timet, 0, ct)
{
if (cur<n && t[cur]==timet)
vx = wx[cur], vy = wy[cur], ++cur;
cur_x -= vx;
cur_y -= vy;
}
return dist(cur_x, cur_y, sx, sy);
}
int main()
{
#ifndef _KEVIN
freopen("joy.in","r",stdin);
freopen("joy.out","w",stdout);
#endif
scanf("%lf %lf %lf %lf", &sx, &sy, &fx, &fy);
scanf("%d %d %lf", &n, &k, &max_v);
F(i, 0, n)
scanf("%d %lf %lf", t+i, wx+i, wy+i);
int div;
for (div=0; div<=k+3; ++div)
if (get_dist(div) <= div * max_v)
break;
if (div > k)
return puts("No"), 0;
int cur = 0;
double vx = 0, vy = 0;
double cur_x = fx, cur_y = fy;
F(timet, 0, div)
{
if (cur<n && t[cur]==timet)
vx = wx[cur], vy = wy[cur], ++cur;
cur_x -= vx;
cur_y -= vy;
}
if (!div)
++div;
double dis = dist(cur_x, cur_y, sx, sy);
double dx = max_v * (cur_x - sx) / dis, dy = max_v * (cur_y - sy) / dis;
puts("Yes");
// 以最快速度飞到终点
cur = vx = vy = 0;
cur_x = sx, cur_y = sy;
F(timet, 0, div-1)
{
if (cur<n && t[cur]==timet)
vx = wx[cur], vy = wy[cur], ++cur;
cur_x += dx + vx;
cur_y += dy + vy;
printf("%f %f\n", cur_x, cur_y);
}
// 不动
F(timet, div, k+1)
printf("%f %f\n", fx, fy);
}
[K]Kebab House
题意
给定n段时间，每一秒钟可以有0和1两种状态。相邻两个0之间的距离必须大于t，而且给定的n段时间中，每一段的1的数量必须不小于某个定值。求度过这段时间有多少种取值方案。
题解
DP。
代码
有待补充
总结&吐槽
这场比赛的前半段时间发挥很好，罚时很少，开题速度很快。中期有一段时间有些浪费，但是节奏还可以。当做到中档题的时候，卡题现象及其严重，有些大众题目没有及时做出来，导致在后面的时间被别的队反超。以后需要加强中档题的练习，锻炼思维能力，有一些想法就及时写下来，要保证一直有人在敲代码，提升中后期效率。
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: ACM暑期集训第七场
本文地址: ACM暑期集训第七场
