A. Right-Left Cipher

乱搞就行

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 100005
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m;
char a[Max];
int main()
{
    scanf("%s",a+1);
    n=strlen(a+1);
    if(n%2==0)
    for(int i=n/2;i>=1;i--)
    {
        printf("%c%c",a[i],a[n-i+1]);
    }
    if(n%2==1)
    {
        putchar(a[n/2+1]);
        for(int i=n/2;i>=1;i--)
            putchar(a[n-i+1]),putchar(a[i]);
    }
}

B. Div Times Mod

暴力枚举n的因数作为\left \lfloor \frac{x}{k} \right \rfloor和x~mod~k就行了

时间复杂度:O(\sqrt n)

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 100005
using namespace std;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll n,k,ans=1e16;
il void check(ll a,ll b)
{
    ans=min(ans,a*k+b);
}
int main()
{
    n=read(),k=read();
    for(int i=1;i*i<=n;i++)
    {
        ll a1=i,a2=n/i;
        if(n%i!=0||a2>=k) continue;
        check(a1,a2);
    }
    for(int i=1;i*i<=n;i++)
    {
        ll a1=n/i,a2=i;
        if(n%i!=0||a2>=k) continue;
        check(a1,a2);
    }
    printf("%I64d\n",ans);
}

C. Connect Three

我做法很复杂

沙雕题能做成这样也没谁了

先对x排个序

然后暴力枚举一个点，使所有点到它的距离和最小且最大的距离最小

然后乱输出所有点走到这个点就完事了

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 100005
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,sx=1000,sy=1000,ax,ay,tx,ty,q[2][Max],cnt=0x3f3f3f3f,d[233],ansd=0x3f3f3f3f;
bool s[1005][1005];
struct node
{
    int x,y;
}e[Max<<1];
il bool cmp(node a,node b)
{
    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}
il void calc(int x,int y)
{
    int res=0,maxd=0;
    for(int i=1;i<=n;i++)
    {
        d[i]=abs(e[i].x-x)+abs(e[i].y-y);
        maxd=max(maxd,d[i]);
        res+=d[i];
    }
    if(res==cnt&&maxd<ansd) cnt=res,ansd=maxd,ax=x,ay=y;
    else if(res<cnt) cnt=res,ansd=maxd,ax=x,ay=y;
}
il void print(int i)
{
    for(int x=min(e[i].x,ax);x<=max(e[i].x,ax);x++)
        if(!s[x][ay]) printf("%d %d\n",x,ay),s[x][ay]=1;
    for(int y=min(e[i].y,ay);y<=max(e[i].y,ay);y++)
        if(!s[e[i].x][y]) printf("%d %d\n",e[i].x,y),s[e[i].x][y]=1;
}
int main()
{
    n=3;
    for(int i=1;i<=n;i++)
    {
        e[i].x=read(),e[i].y=read();
        sx=min(sx,e[i].x),sy=min(sy,e[i].y);
        tx=max(tx,e[i].x),ty=max(ty,e[i].y);
    }
    //cout<<sx<<" "<<ty<<' '<<tx<<' '<<ty<<endl;
    sort(e+1,e+1+n,cmp);
    for(int i=sx;i<=tx;i++)
        for(int j=sy;j<=ty;j++)
        {
            calc(i,j);
        }
    cout<<cnt+1<<endl;
    for(int i=1;i<=n;i++)
    {
        print(i);
    }
}

结束后

（为什么每次想到了D或者差点调出D来结果比赛就结束了来不及调/写

还是菜的真实（

D. Minimum Diameter Tree

设度为1的节点的个数为c,那么答案就为\frac{2s}{c}

为什么这是对的呢

因为直径一定连接了两个度为1的点

考虑如何摆放权值

可以发现只要把权值分散到直径的端点就可以了

如果放在中间可能会有多条直径穿过而产生更差的解

所以可以贪心的把全部权值分散到度为1的节点

因此最大直径长度就为\frac{2s}{c}了

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 100005
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
double s;
ll n,in[Max],ans;
int main()
{
    n=read();
    cin>>s;
    for(int i=1;i<n;i++)
        in[read()]++,in[read()]++;
    for(int i=1;i<=n;i++)
        if(in[i]==1) ans++;
    printf("%.8f",(double)2.0*s/ans);
}

这么简单的结论我为什么就不早点想到,太菜了

然后其他的题就不会了

rating日常爆炸

1545835850637

1545835875057

完了我马上expert就要没了