2019牛客暑期多校训练营（第十场）
B Coffee Chicken
题目链接
题意：字符串s[1]为"COFFEE"，s[2]为"CHICKEN"。其中字符串s[n]为s[n-2]+s[n-1]。给定n和k，求第n个字符串的第k个字符开始连续的10个字符，当字符小于10个则输至字符串末尾。
思路：递归，根据字符串递归转移长度和下标。
#include <bits/stdc++.h>
#define maxn 505
typedef long long ll;
using namespace std;
int n;
ll k;
string s[3];
ll len[maxn];
void init(){
len[1]=s[1].size();
len[2]=s[2].size();
for(int i=3;i<55;i++){
len[i]=len[i-2]+len[i-1];
}
}
void input(){
scanf("%d%lld",&n,&k);
}
void solve(int n,ll k,int L){
// cout<<n<<' '<<k<<' '<<L<<endl;
if(n<3){
// cout<<k-1+L<<' '<<len[n]<<endl;
for(int i=k-1;i<min(k-1+L,len[n]);i++)
printf("%c",s[n][i]);
return;
}
if(k+9<=len[n-2])
solve(n-2,k,L);
else if(k>len[n-2])
solve(n-1,k-len[n-2],L);
else{
solve(n-2,k,L);
solve(n-1,1,L-len[n-2]+k-1);
}
}
int main(){
s[1]="COFFEE";
s[2]="CHICKEN";
init();
int t;
scanf("%d",&t);
while(t--){
input();
solve(n,k,10);
printf("\n");
}
} D Han Xin and His Troops
题目链接
题意：给定多组a和b，求满足的x，使得x%b==a，当x大于m和不存在时，输出特定语句，否则输出x
思路：套用扩展中国剩余定理，但存在爆ll情况，使用python、java、或__int128。
#include <bits/stdc++.h>
#define maxn 100005
typedef __int128 ll;
using namespace std;
ll n;ll m;
ll a[maxn],b[maxn];
ll ai[maxn],bi[maxn];
void scan(__int128 &x)//输入
{
x = 0;
int f = 1;
char ch;
if((ch = getchar()) == '-') f = -f;
else x = x*10 + ch-'0';
while((ch = getchar()) >= '0' && ch <= '9')
x = x*10 + ch-'0';
x *= f;
}
void input(){
scan(n);scan(m);
ll i;
for(i=1;i<=n;i++){
scan(a[i]);scan(b[i]);
// scanf("%lld%lld",&a[i],&b[i]);
bi[i]=a[i];
ai[i]=b[i];
}
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0){x=1;y=0;return a;}
ll gcd=exgcd(b,a%b,x,y);
ll tp=x;
x=y; y=tp-a/b*y;
return gcd;
}
ll excrt()
{
ll x,y,k;
ll M=bi[1],ans=ai[1];
//bi被余数，ai余数
for(ll i=2;i<=n;i++)
{
ll a=M,b=bi[i],c=(ai[i]-ans);
ll gcd=exgcd(a,b,x,y),bg=b/gcd;
if(c%gcd!=0) return -1;
x=(x*(c/gcd)%bg+bg)%bg;//快乘
ans+=x*M;
M=M/gcd*b;
}
return ans;
}
void print(__int128 x)
{
if(x < 0)
{
x = -x;
putchar('-');
}
if(x > 9) print(x/10);
putchar(x%10 + '0');
}
void solve(){
__int128 res=excrt();
if(res==-1)
printf("he was definitely lying\n");
else if(res>m)
printf("he was probably lying\n");
else
print(res);
}
int main(){
input();
solve();
} E Hilbert Sort
题目链接
题意：定义希尔伯特曲线在2^k边长图的样子，给出n个点的坐标，求其根据曲线的顺序关系。
思路：对于每一个点递归划分，进行编码，最后根据编码排序。
#include <bits/stdc++.h>
#define maxn 1000005
typedef long long ll;
using namespace std;
int n,k;
struct node{
int x,y;
ll s=0;
}nod[maxn];
bool cmp(node a,node b){
return a.s<b.s;
}
void input(){
scanf("%d%d",&n,&k);
int i;
for(i=1;i<=n;i++)
scanf("%d%d",&nod[i].x,&nod[i].y);
}
ll dg(int x,int y,int k){
// cout<<x<<' '<<y<<' '<<k<<endl;
int d=pow(2,k-1);
if(k==1){
if (x == 1 && y == 1)return 1;
else if (x == 2 && y == 1)return 2;
else if (x == 2 && y == 2)return 3;
else if (x == 1 && y == 2)return 4;
}
if(x<=d&&y<=d){
swap(x,y);
return d*d*1+dg(x,y,k-1);
}
if(x>d&&y<=d)
return d*d*2+dg(x-d,y,k-1);
if(x>d&&y>d)
return d*d*3+dg(x-d,y-d,k-1);
if(x<=d&&y>d){
y=y-d;
y=d-y+1;
x=d-x+1;
swap(x,y);
return d*d*4+dg(x,y,k-1);
}
}
void solve(){
int i;
for(i=1;i<=n;i++){
nod[i].s=dg(nod[i].x,nod[i].y,k);
// cout<<nod[i].s<<endl;
}
sort(nod+1,nod+1+n,cmp);
for(i=1;i<=n;i++)
printf("%d %d\n",nod[i].x,nod[i].y);
}
int main(){
input();
solve();
} F Popping Balloons
题目链接
题意：给你n个气球坐标x,y。你可以选择一个X坐标和Y坐标，使得X，X+R，X+2R线上的所有气球打破，使Y，Y+R，Y+2R上的气球也打破。求最多能打破多少个气球。
思路：枚举一维，例如枚举X。我们需要logn的求出最大的sum[Y]+sum[Y+R]+sum[Y+2*R]，记录每个x轴上y的坐标，每次枚举时我们就可以将这些y坐标的共享-1,查询后再+1。
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,r;
int sum[maxn<<2];
int tot[maxn];
vector <int>v[maxn];
void PushUp(int rt){
sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}
void Build(int l,int r,int rt){
if(l==r){
sum[rt]=0;
return;
}
int mid=(l+r)>>1;
Build(l,mid,rt<<1);
Build(mid+1,r,rt<<1|1);
PushUp(rt);
}
void update(int index,int x,int l,int r,int rt){
if(l==r)
{
sum[rt]+=x;
return;
}
int mid=(l+r)>>1;
if(index<=mid) update(index,x,l,mid,rt<<1);
else update(index,x,mid+1,r,rt<<1|1);
PushUp(rt);
}
void update(int index,int x){
update(index,x,1,100001,1);
if(index-r>0)
update(index-r,x,1,100001,1);
if(index-2*r>0)
update(index-2*r,x,1,100001,1);
}
void input(){
scanf("%d%d",&n,&r);
int i,x,y;
Build(1,100001,1);
for(i=1;i<=n;i++){
scanf("%d%d",&x,&y);
x++;y++;
tot[y]++;
v[x].push_back(y);
}
for(i=1;i<=100001;i++){
if(i+r<=100001)
tot[i]=tot[i]+tot[i+r];
if(i+2*r<=100001)
tot[i]=tot[i]+tot[i+2*r];
update(i,tot[i],1,100001,1);
}
}
void solve(){
int SUM,i,j;
int ans=0;
for(i=1;i<=100001;i++){
SUM=v[i].size();
if(i+r<=100001)
SUM+=v[i+r].size();
if(i+2*r<=100001)
SUM+=v[i+2*r].size();
int x=i;
for(j=0;j<v[x].size();j++)
update(v[x][j],-1);
if(x+r<=100001){
for(j=0;j<v[x+r].size();j++)
update(v[x+r][j],-1);
}
if(x+2*r<=100001){
for(j=0;j<v[x+2*r].size();j++)
update(v[x+2*r][j],-1);
}
// cout<<SUM<<' '<<sum[1]<<endl;
ans=max(ans,SUM+sum[1]);
for(j=0;j<v[x].size();j++)
update(v[x][j],1);
if(x+r<=100001){
for(j=0;j<v[x+r].size();j++)
update(v[x+r][j],1);
}
if(x+2*r<=100001){
for(j=0;j<v[x+2*r].size();j++)
update(v[x+2*r][j],1);
}
}
printf("%d",ans);
}
int main(){
input();
solve();
} H Stammering Chemists
题目链接
题意：给你一个6个结点的树，判断为题目中的哪一种树。
思路：根据树的度、节点判断。
#include <bits/stdc++.h>
#define maxn 10
using namespace std;
int indeg[maxn];
vector <int>G[maxn];
void input() {
int i;
int x, y;
for (i = 0; i<5; i++) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
indeg[x]++;
indeg[y]++;
}
}
void solve() {
int i;
int maxx1 = -1, maxx2 = -1;
int maxi = -1;
for (i = 1; i <= 6; i++)
{
if (indeg[i]>maxx1) {
maxx2 = maxx1;
maxx1 = indeg[i];
maxi = i;
}
else if (indeg[i]>maxx2) {
maxx2 = indeg[i];
}
}
if (maxx1 == 4)
printf("2,2-dimethylbutane\n");
else if (maxx1 == 2)
printf("n-hexane\n");
else if (maxx1 == 3 && maxx2 == 3)
printf("2,3-dimethylbutane\n");
else {
int cnt = 0;
for (i = 0; i<G[maxi].size(); i++) {
if (indeg[G[maxi][i]] == 1)
cnt++;
}
if (cnt == 2)
printf("2-methylpentane\n");
else
printf("3-methylpentane\n");
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
memset(indeg, 0, sizeof indeg);
for (int i = 1; i <= 6; i++)
G[i].clear();
input();
solve();
}
}
京公网安备 11010502036488号