[游戏开发]atcoder:arc129（abc）abc228(abc)题解

arc129

A题：

题意：

输入N,L,R，求L~R这个区间内，有多少个数与N异或运算后小于N？（N^X<N）。

思路：

异或运算：在二进制下，0^0=1,1^1=0,0^1=1,1^0=1.

不难发现，当一个数的最高位1与同位置的1异或后，得到的数一定小于本身。所以只需要反复找N中的1位然后与该位置为1的数异或，结果一定小于本身。最后需要注意数在区间l-r即可。

代码如下：

#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<sstream>

using namespace std;

typedef long long ll;

ll qpow(ll a,ll b)
{
    int ans=1;
    while(b>0)
    {
        if(b&1)
        {
            ans*=a;
        }
        a*=a;
        b>>=1;
    }
    return ans;
}

int main(void)
{
    int t=1;
    ll n,l,r;
    //cin>>t;
    cin>>n>>l>>r;
    ll res=0;
    for(int i=62;~i;i--)
    {
        if(n>>i&1)
        {
            ll lls=max(l,1ll<<i);
            ll rrs=min(r,(1ll<<(i+1))-1);
            if(rrs>=lls)
                res+=rrs-lls+1;
        }

    }
    cout<<res<<endl;
}

B题：

题意：

有以下三个函数：

• If?x<lx<l:?dist(l,r,x)=l-xdist(l,r,x)=l?x
• If?l \leq x \leq rl≤x≤r:?dist(l,r,x)=0dist(l,r,x)=0
• If?r<xr<x:?dist(l,r,x)=x-rdist(l,r,x)=x?r

输入N组, l r，找到 一个值X使得max(dist1,dist2,dist3...distN)的值最小。

思路 ：

dist(l,r,x)=max(0,l-x,x-r)。

所以我们要找到使max(0,l1-x,x-r1,l2-x,x-r2......ln-x,x-rn)最小。

易知，当l最大时x-l最小，当r最小时，r-x最小，max（0，lmin-x,rmin-x）最小。

代码如下

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int maxs=0,mins=1e9+1;
    for(int i=0,L,R;i<n;i++)
    {
        cin>>L>>R;
        maxs=max(maxs,L);
        mins=min(mins,R);
        if(maxs<=mins)
            cout<<0<< endl;
        else {
            int opt=(maxs+mins)/2;
            cout<<maxs-opt<<endl;
        }
    }
}

C题：

题意：输入一个n，输出一个由1-9组成的字符串，使得该串中有n对数连接起来是7的倍数。

例如输入2,输出142

(1,2)(2,3)加起来得14,42，共2对是7的对数。

思路：

不太会

一对整数 (l,r) 满足条件当且仅当 (al ?ar+1 ) /10∣s∣?r 可以被 7 整除。这里，10∣s∣?r 与 7?互质，所以上面等价于 a_l-a_{r+1}al -ar+1 可被 7 整除。

设bi 为ai 除以 7 的余数。另外，对于每个0≤v<7，设 cv 的 i 数使得 bi =v。

有 N 对整数 (l, r)(l,r) 满足条件当且仅当存在 N 对(l,r) 使得bl = br+1 ，可以进一步改写为∑0≤v<7 cv (cv ?1)/2=N .

让我们首先尝试找到满足上述条件的 c_vcv。我们可以贪婪地这样做。具体来说，我们应该按照这个顺序决定c_0,c_1,\cdots,c_6c0 ,c1 ,?,c6 ，并且在选择c_kck 时，我们应该选择满足\sum_{0 \leq v \leq k} c_v(c_v-1)/2 \leq N∑0≤v≤k cv (cv ?1)/2≤N。

这种贪婪策略在此问题的约束下为所有 NN 找到理想的 c_vcv。 （它不适用于一般的N，但我们可以使用 Fermat 多边形数定理使其工作。）

找到 c_vcv 之后，让我们根据它们来决定 bi。当bi+1 已经确定后，我们可以通过将 s 的第 ii 个字符适当设置为 1、2、?或 7 来自由选择 bi 的值，因此整个构造可以向后做。

代码如下：

#include <bits/stdc++.h>

using namespace std;

int n,vis[2][7];

void init()
{
	memset(vis[1],0,sizeof(vis[1]));
	for (int i=0;i<7;i++)
    {
		if (vis[0][i])
		{
		    vis[1][(3*i)%7]=1;
        }
	}
	for (int i=0;i<7;i++)
    {
        vis[0][i]=vis[1][i];
    }
}

void solve (int n)
{
	int tmp=0;
	while (tmp*(tmp+1)/2<=n)
    {
        tmp++;
    }
	for (int i=1;i<=tmp-1;i++)
    {
        cout<<7;
		init();
	}
	init();
	n-=tmp*(tmp-1)/2;
	if (n==0)
	{
	    return;
    }
	for (int i=1;i<7;i++)
    {
		if (!vis[0][i])
		{
			printf("%d",(7-i)%7);
			memset(vis[1],0,sizeof(vis[1]));
			for (int j=0;j<7;j++)
            {
				if (vis[0][j]) {vis[1][(j+7-i)%7]=1;}
			}
			for (int j=0;j<7;j++)
            {
                vis[0][j]=vis[1][j];
            }
			vis[0][(7-i)%7]=1;
			break;
		}
	}
	solve(n);
	return;
}
int main ()
{
	scanf("%d",&n);
	solve(n);
	printf("\n");
	return 0;
}

abc228(a,b,c)题解

A题

题意 在 S-T这段时间里，灯会亮，那么请问在X过后的30分钟那一刻灯是不是亮的？

思路：直接判断

代码如下：

#include <bits/stdc++.h>

using namespace std;

int n,vis[2][7];

int main(void)
{
    int s,t,x;
    cin>>s>>t>>x;
    double k=x+0.5;
    if(s<t)
    {
        if(k>=s&&k<=t)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    else
    {
         if(k<s&&k>t)
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
    }
}

B题：

题意

有N个人，第N个人的好朋友是Fi

一个人的秘密被第x个人知道了，这个人会把这个秘密告诉他的好朋友，最后有多少人知道这个秘密？

思路：

知道秘密的好朋友设为-1，直到好朋友是-1的人知道秘密结束。

代码如下：

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
    int f[100005];
    int a;
    int n,x;
    cin>>n>>x;
    for(int i=1;i<=n;i++)
        cin>>f[i];
    int ans=0;
    while(f[x]!=-1)
    {
        a=f[x];
        f[x]=-1;
        x=a;
        ans++;
    }
    cout<<ans<<endl;
}

C题：

题意：

N个人，每个人前三天的分数给出了，请问他有没有可能通过第四天的考试最后总分排在前K？

思路：

先排序，找到前三天第N名的分数，然后假设自己考满分，别人都是0分，看能否排在前K。

代码如下：

#include <bits/stdc++.h>

using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}

int main(void)
{
    int n,x;
    cin>>n>>x;
    int p[100005],tool[100005];
    int a,b,c;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b>>c;
        p[i]=a+b+c;
        tool[i]=p[i];
    }
    sort(tool+1,tool+n+1,cmp);
    int ant=tool[x];
    for(int i=1;i<=n;i++)
    {
        if(p[i]+300>=ant)
            {
                cout<<"Yes"<<endl;
              //  cout<<p[i]<<" "<<ant<<endl;
            }
        else
            cout<<"No"<<endl;
    }
}