A Golden Spirit

策略肯定是先将左右的人互换的对面,互换位置后,此时你的位置是在左边,考虑是否要等待左边呆得最久的人休息完,或者提前过去右边等待右边呆的最久的人休息完。两个策略取max.

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

const int maxn=2e5+10;

typedef unsigned long long ll;

int main()
{
    int t;
    scanf("%d",&t);
    while( t-- )
    {
        ll n,x,t;
        scanf("%lld%lld%lld",&n,&x,&t);
        ll ans1=4*n*t;
        ll ans2=4*n*t;
        if( 2*(n-1)*t+2*t<x ) ans2+=x-(2*(n-1)*t+2*t)+t;
        else ans2+=t;
        if( 2*(n-1)*t<x ) ans1+=(x-2*(n-1)*t);

        printf("%lld\n",min(ans1,ans2));
    }
} 

D ABC Conjecture

对着1e18的数据范围干瞪眼可不行,直接打表发现满足的数进行素数拆分至少有一个素数的指数是大于1的,否则就不满足。并且因为1e6*1e6=1e12我们只需要筛1e6的素数就可以,剩下未被筛到的素数直接sqrt判断。(区域赛常考点)

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

const int maxn=1e6+10;

typedef long long ll;
int prime[5000000];//保存素数
int vis[maxn];     //初始化
int cnt;

void getprime(int n)
{
    cnt=0;
    memset(vis,0,sizeof(vis));
    for(int i=2;i<n;i++)
    {
        if(vis[i]==0)
            prime[cnt++]=i;
        for(int j=0;j<cnt&&i*prime[j]<n;j++)
        {
            vis[i*prime[j]]=1;
            // vis[i*prime[j]]=prime[j]; 
            if(i%prime[j]==0)
                break;
        }
    }
}


int main()
{
    getprime(maxn-2);
    int n,q;
    scanf("%d",&q);
    while( q-- )
    {
        ll x;scanf("%lld",&x);
        bool flag=false;
        for( int i=0;prime[i]<=x&& i<cnt;i++ )
        {
            if( x%(prime[i]*prime[i])==0 )
            {
                flag=true;
                break;
            }
            if( x%prime[i]==0 ) x/=prime[i];
        }
        if( x>1 )
        {
            ll t=sqrt(x);
            if( t*t==x ) flag=true;
        }
        if( flag ) puts("yes");
        else puts("no");

    }
} 

L Clock Master

我们选取齿轮肯定最好两个齿轮没有公因子,那么就是两个齿轮数互质,这样方案数就是每个数相乘。那么所有数都是互质肯定是枚举所有质数的幂次数进行选择,每个质数的幂次数值选取一个,那么就是分组背包。考虑到可能会MLE滚动优化了一下(其实应该不会.
(坑点,记得预处理log(i)否则会把你T自闭)

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

const int maxn=3e5+10;

typedef long long ll;
int prime[maxn];//保存素数
int vis[maxn];     //初始化
int cnt;

void getprime(int n)
{
    cnt=0;
    memset(vis,0,sizeof(vis));
    for(int i=2;i<n;i++)
    {
        if(vis[i]==0)
            prime[cnt++]=i;
        for(int j=0;j<cnt&&i*prime[j]<n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0 )
                break;
        }
    }
}
double dp[2][30005];
double Log[30045];

int main()
{
//    clock_t clock_start1 = clock();
    getprime(30005);
    for( int i=1;i<=3e4;i++ ) Log[i]=log(i);
    int op=1,up=30000;
//    for( int i=0;i<=up;i++ ) dp[0][i]=dp[1][i]=0;

    for( int i=0;i<cnt && prime[i]<=up;i++ )
    {
        int now=prime[i];
        for( ;now<=up;now*=prime[i] )
        {
            for( int j=up;j>=now;j-- )
            {
                dp[op][j]=max(dp[op^1][j-now]+Log[now],dp[op][j]);
            }
        }
        op^=1;
        for( int j=up;j>=0;j-- ) dp[op][j]=max(dp[op][j],dp[op^1][j]);
    }
//    clock_t clock_end1 = clock();
//    printf("testee time:  %ld ms  ", clock_end1 - clock_start1);
    op^=1;
    int t;
    scanf("%d",&t);
    while( t-- )
    {
        int x;scanf("%d",&x);
        printf("%.9lf\n",dp[op][x]);
    } 
//    

}