比赛地址
[B]Coffee Chicken
题意
定义F[1]="COFFEE",F[2]="CHICKEN",且有F[n]=F[n-2]+F[n-1]。求F[n]第k位向后的十个字符。
题解
根据所求字符位置递归求解。
代码
#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 1000000000000
using namespace std;
LL T,n,k,i;
string c1,c2;
LL s[510],from[510];
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,j=0;
s[1]=6; s[2]=7;
for (i=3;i<=500;i++){
s[i]=s[i-2]+s[i-1];
if (s[i]>=INF) break;
}
s[i+1]=s[i]+s[i-1];
for (j=i+2;j<=500;j++)
s[j]=INF+19,from[j]=(j-i)%2?(i+1):i;
}
inline void Find(int x,LL y,LL l){
int i=0;
if (s[x]==INF+19){
Find(from[x],y,l);
return;
}
if (x==1){
for (i=0;i<l;i++)
printf("%c",c1[y-1+i]);
return;
}
if (x==2){
for (i=0;i<l;i++)
printf("%c",c2[y-1+i]);
return;
}
if (y+l-1<=s[x-2]) Find(x-2,y,l);
else if (y>s[x-2]) Find(x-1,y-s[x-2],l);
else Find(x-2,y,s[x-2]-y+1),Find(x-1,1,l+y-1-s[x-2]);
}
int main(){
scanf("%lld",&T);
Ready();
c1="COFFEE";
c2="CHICKEN";
while (T--){
scanf("%lld%lld",&n,&k);
Find(n,k,Min(10,s[n]-k+1));
cout<<endl;
}
return 0;
}
[D]Han Xin and His Troops
题意
给定n个同余方程(模数可能不是质数)，求在给定范围内是否有解。
题解
中国剩余定理。
对于不是质数的情况，要将所有的模数进行拆分。求出所有模数的LCM后，保留下每个模数含有的LCM中最大的质数次幂。余数不变，然后套用中国剩余定理求解。因为这道题的n比较小，所以也可以依次求解每个方程。
代码
p = [0] * 10000000
b = [0] * 1000005
w = [0] * 1000005
rem = [-1] * 1000005
def shai() :
p[1] = 1
for i in range(2, 200000) :
if p[i] == 0 :
p[i] = i
for j in range(i, 200000//i) :
if (p[i*j]==0) :
p[i*j] = i
def extended_euclid(a, b) :
if b == 0 :
return (a, 1, 0)
else :
res, x, y = extended_euclid(b, a%b)
t = x
x = y
y = t-(a//b)*y
return (res, x, y)
'''
def modular(a, b, n) :
d, x, y = extended_euclid(a, n)
if b%d != 0 :
return -1
else :
e = (x*(b//d))%n
for i in range(d) :
print(e+i*(n//d)%n, end = " its modular\n")
'''
def china(b, w, lent) :
x = 0
n = 1
for i in range(lent) :
n *= w[i]
for i in range(lent) :
m = n//w[i]
d, xx, y = extended_euclid(w[i], m)
x = (x+y*m*b[i])%n
return (n+(x%n))%n
shai()
n, m = map(int, input().split())
flag = 1
for i in range(n) :
a, y = map(int, input().split())
while(a > 1) :
k = p[a]
kk = 1
while(a//k*k == a) :
kk *= k
a = a//k
if rem[kk] == -1 :
rem[kk] = y%kk
else :
if rem[kk] != y%kk :
flag = 0
for i in range(2, 100000) :
aim = 0
if p[i] == i :
kk = i
aim = 0
while kk < 100000 :
if rem[kk] != -1 :
aim = kk
kk *= i
if aim == 0 :
continue
aim_rem = rem[aim]
kk = i
while kk < aim :
if rem[kk] == -1 :
kk *= i
continue
if rem[kk] != aim_rem%kk :
flag = 0
break
rem[kk] = -1
kk *= i
if flag == 0 :
break
ll = 0
for i in range(100000) :
if rem[i] != -1:
b[ll] = rem[i]
w[ll] = i
ll += 1
if flag == 1 :
ans = china(b, w, ll)
if flag == 0 :
print("he was definitely lying")
elif ans > m :
print("he was probably lying")
else :
print(ans)
[E]Hilbert Sort
题意
按照希尔伯特曲线对给定的方格进行排序。
题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
struct point {
long long int x, y, s;
}kk[1000005];
int n, k;
long long int mi[1000005];
long long int find(long long int x, long long int y, int k, long long int ans) {
if (k == 0) return ans;
if (x <= mi[k-1] && y <= mi[k-1]) return find(y, x, k-1, ans*4);
if (x <= mi[k-1] && y > mi[k-1]) return find(x, y-mi[k-1], k-1, ans*4+1);
if (x > mi[k-1] && y > mi[k-1]) return find(x-mi[k-1], y-mi[k-1], k-1, ans*4+2);
x -= mi[k-1];
return find(mi[k-1]-y+1, mi[k-1]-x+1, k-1, ans*4+3);
}
bool cmp(point a, point b) { return a.s < b.s; }
int main(){
mi[0] = 1;
for (int i = 1; i <= 30; i++) mi[i] = mi[i-1] * 2;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &kk[i].y, &kk[i].x);
kk[i].s = find(kk[i].x, kk[i].y, k, 0);
}
sort(kk+1, kk+n+1, cmp);
for (int i = 1; i <= n; i++) printf("%lld %lld\n", kk[i].y, kk[i].x);
return 0;
}
[F]Popping Balloons
题意
在坐标轴上有n个气球。然后可以横向或者纵向开枪，每当沿一个坐标横向(纵向)开枪时，所有这一水平(垂直)高度的气球都会被打掉。横纵各可以开三枪，要求三枪中相邻两枪的距离间隔是r。求最多能打掉多少气球。
题解
假如横向开枪策略已经制定，则将这三个水平方向上的气球全部去掉后，纵向开枪方案一定是剩下气球按要求开枪能打中的最多的三列。正确性显然。所以考虑枚举横向开枪的方案。
维护一个数列，记录每个纵向坐标上有多少气球。每当枚举到一个横向坐标，把以该坐标为第一枪，一共三枪所打掉的气球的纵坐标全部标记出来，在维护的数列中减去相对应的值。然后建一棵线段树，每个叶子节点维护一个三元组(i,i+r,i+2r)，表示这种纵向开枪方式能打掉的气球个数。同时维护最大值。每当横向气球处理完毕后，当前方案的答案便是横向打掉的气球数加上纵向开枪方案的最大值。最后统计答案即可。
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 300010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i,x,y,s,cnt,Ans,r,j;
struct Tree{
int l,r,d;
}t[N*8];
vector <int> v[N];
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 Maketree(int x,int low,int high){
int mid=(low+high)>>1;
t[x].l=low; t[x].r=high;
if (low==high) return;
Maketree(l(x),low,mid); Maketree(r(x),mid+1,high);
}
inline void Add(int x,int low,int p){
int mid=(t[x].l+t[x].r)>>1;
if (t[x].l==t[x].r){
t[x].d+=p; return;
}
if (low<=mid) Add(l(x),low,p); else Add(r(x),low,p);
t[x].d=Max(t[l(x)].d,t[r(x)].d);
}
int main(){
scanf("%d%d",&n,&r);
for (i=1;i<=n;i++){
scanf("%d%d",&x,&y);
v[x].push_back(y);
}
Maketree(1,0,100000);
Ans=0;
for (i=0;i<=100000;i++)
for (j=0;j<v[i].size();j++){
Add(1,v[i][j],1);
if (v[i][j]>=r) Add(1,v[i][j]-r,1);
if (v[i][j]>=2*r) Add(1,v[i][j]-2*r,1);
}
for (i=0;i<=100000;i++){
// if (i+2*r>100000) break;
s=i;
for (j=0;j<v[s].size();j++){
Add(1,v[s][j],-1);
if (v[s][j]>=r) Add(1,v[s][j]-r,-1);
if (v[s][j]>=2*r) Add(1,v[s][j]-2*r,-1);
}
s=i+r;
if (s<=100000){
for (j=0;j<v[s].size();j++){
Add(1,v[s][j],-1);
if (v[s][j]>=r) Add(1,v[s][j]-r,-1);
if (v[s][j]>=2*r) Add(1,v[s][j]-2*r,-1);
}
}
s=i+2*r;
if (s<=100000){
for (j=0;j<v[s].size();j++){
Add(1,v[s][j],-1);
if (v[s][j]>=r) Add(1,v[s][j]-r,-1);
if (v[s][j]>=2*r) Add(1,v[s][j]-2*r,-1);
}
}
cnt=0;
cnt=v[i].size()+v[i+r].size()+v[i+2*r].size();
cnt+=t[1].d;
Ans=Max(Ans,cnt);
s=i;
for (j=0;j<v[s].size();j++){
Add(1,v[s][j],1);
if (v[s][j]>=r) Add(1,v[s][j]-r,1);
if (v[s][j]>=2*r) Add(1,v[s][j]-2*r,1);
}
s=i+r;
if (s<=100000){
for (j=0;j<v[s].size();j++){
Add(1,v[s][j],1);
if (v[s][j]>=r) Add(1,v[s][j]-r,1);
if (v[s][j]>=2*r) Add(1,v[s][j]-2*r,1);
}
}
s=i+2*r;
if (s<=100000){
for (j=0;j<v[s].size();j++){
Add(1,v[s][j],1);
if (v[s][j]>=r) Add(1,v[s][j]-r,1);
if (v[s][j]>=2*r) Add(1,v[s][j]-2*r,1);
}
}
}
cout<<Ans<<endl;
return 0;
}
[H]Stammering Chemists
题意
给定一个己烷的碳原子的链接方式，求这种分子是哪种同分异构体。
题解
签到题
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#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)
constexpr int MN(12);
struct Ed
{
Ed *next;
int v;
} ed[MN*2], *head[MN];
int dep;
bool vis[MN];
void dfs(int u, int de)
{
if (de > dep)
dep = de;
for (Ed *p=head[u]; p; p=p->next)
{
int v = p->v;
if (!vis[v])
{
vis[v] = true;
dfs(v, de+1);
}
}
}
int main()
{
int tot;
int ind[MN];
int indnt[MN];
#define edd(uu, vv) ed[++tot].next=head[uu], ed[tot].v=vv, head[uu]=ed+tot
int T;
sc(T)
while (T--)
{
head[0] = head[1] = head[2] = head[3] = head[4] = head[5] = head[6] = head[7] = NULL;
ind[0] = ind[1] = ind[2] = ind[3] = ind[4] = ind[5] = ind[6] = ind[7] = 0;
indnt[0] = indnt[1] = indnt[2] = indnt[3] = indnt[4] = indnt[5] = indnt[6] = indnt[7] = 0;
tot = 0;
int u, v;
sc(u)sc(v) ++ind[u], ++ind[v]; edd(u, v); edd(v, u);
sc(u)sc(v) ++ind[u], ++ind[v]; edd(u, v); edd(v, u);
sc(u)sc(v) ++ind[u], ++ind[v]; edd(u, v); edd(v, u);
sc(u)sc(v) ++ind[u], ++ind[v]; edd(u, v); edd(v, u);
sc(u)sc(v) ++ind[u], ++ind[v]; edd(u, v); edd(v, u);
++indnt[ind[1]];
++indnt[ind[2]];
++indnt[ind[3]];
++indnt[ind[4]];
++indnt[ind[5]];
++indnt[ind[6]];
if (indnt[1]==4)
{
if (indnt[3]==2)
puts("2,3-dimethylbutane");
else
puts("2,2-dimethylbutane");
}
else if (indnt[1]==2)
{
puts("n-hexane");
}
else
{
dep = 0;
vis[0] = vis[1] = vis[2] = vis[3] = vis[4] = vis[5] = vis[6] = vis[7] = 0;
for (u=1; u<=6; ++u)
if (ind[u]==3)
{
vis[u] = 1;
dfs(u, 1);
break;
}
if (dep == 3)
puts("3-methylpentane");
else
puts("2-methylpentane");
}
}
return 0;
}
总结&吐槽
这场比赛是牛客系列比赛的最后一场，至此牛客上的训练落下帷幕。前面几场没有打实在是有点亏，心疼报名费
这场比赛的主要问题在于解题的速度和思维灵活程度的不足。D题是明显的中国剩余定理，为了防止爆long long拿Python调了很久。其实看到这道题过了那么多，应该考虑到使用暴力求解的，这样就不会耗费全队的想题时间了。F题也是水题，一开始的思路有点偏，直到交了三发错误的贪心后我才受到启发拿线段树求各状态最值。这两道题的罚时实在是可惜。最后结果就是J题的DP没有时间去推优化的式子了，而且到最后也没有开出新的题目。
以后应该思路灵活一些，该暴力就暴力，速度开题，不能在一道题上耽误过多时间。希望之后有所提升。
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: ACM暑期集训第六场
本文地址: ACM暑期集训第六场
