ZJNU-12-06 组队赛

A-Simple Calculator

题意：

给了两个数x，y。现在给你两个按钮，按钮A将x+1，按钮B将x的符号翻转，问最少要多少次操作，使x=y。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int x,y;
int main()
{
   
    scanf("%d%d",&x,&y);
    if(x>0&&y>0)
    {
   
        if(x>y)
            printf("%d",x-y+2);
        else
            printf("%d",y-x);
    }
    else if(x>0&&y<0)
    {
   
        if(x>-y)
            printf("%d",1+x+y);
        else
            printf("%d",1-x-y);
    }
    else if(x<0&&y<0)
    {
   
        if(x<y)
            printf("%d",y-x);
        else
            printf("%d",2+x-y);
    }
    else if(x<0&&y>0)
    {
   
        if(-x>y)
            printf("%d",1-x-y);
        else
            printf("%d",1+x+y);
    }
    else if(x==0)
    {
   
        if(y>=0)
            printf("%d",y);
        else
            printf("%d",1-y);
    }
    else
    {
   
        if(x>0)
            printf("%d",1+x);
        else
            printf("%d",-x);
    }
    return 0;
}

B-Contiguous Repainting

题意：

给了你一个长度为n的数组，每次你能将连续k个数涂成黑色或白色，可覆盖，可以填任意多次，问黑色方块上的数加起来最多为多少。

solution：

根据题意分析，可以知道可以先取出k个数特判，其余的只要贪心的取正数即可。因此先将正数的和求出来，然后每k个数判断一下加上负数和或者去掉正数和哪种情况更优，取个max。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int n,k;
int a[100005];
ll maxn=0,tem=0;
int main()
{
   
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
   
        scanf("%d",&a[i]);
        if(a[i]>0)tem+=a[i];
    }
    ll zh=0,fu=0;
    for(int i=0;i<k;i++)
    {
   
        if(a[i]>0)zh+=a[i];
        else fu+=a[i];
    }
    if(zh>-fu)maxn=max(maxn,tem+fu);
    else maxn=max(maxn,tem-zh);
    for(int i=k;i<n;i++)
    {
   
        if(a[i-k]>0)zh-=a[i-k];
        else fu-=a[i-k];
        if(a[i]>0)zh+=a[i];
        else fu+=a[i];
        if(zh>-fu)maxn=max(maxn,tem+fu);
        else maxn=max(maxn,tem-zh);
    }
    printf("%lld",maxn);
    return 0;
}

C-Tetromino Tiling

题意：

给出几种俄罗斯方块的个数，让你求最多用k个俄罗斯方块能拼成高度为2，长为2k的矩形。矩形必须是实心的。

solution：

先求出如何用俄罗斯方块拼成完整的矩形。发现第三个、第六个、第七个没有用处。2个第一种；或1个第二种；或2个第四种；或2个第五种，或奇数个第一种，1个第四种，1个第五种；或偶数个第一种，2个第四种；或偶数个第一种，2个第五种。
然后贪心求解。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
ll a[10];
int main()
{
   
    for(int i=0;i<7;i++)scanf("%lld",&a[i]);
    ll res=0;
    res=a[0]/2*4+a[1]*2+a[3]/2*4+a[4]/2*4;
    if(a[0]%2)
    {
   
        if(a[3]&&a[4])
        {
   
            if(a[3]%2==1&&a[4]%2==1)
                res+=6;
            else if(a[3]%2==1)
                res+=2;
            else if(a[4]%2==1)
                res+=2;
        }
    }
    else if(a[0])
    {
   
        if(a[3]%2==1&&a[4]%2==1)
            res+=2;
    }
    printf("%lld",res/2);
    return 0;
}

D-K-th K

题意：

给了你一个长度为n的数组x，让你构造一个数组使得i第i次出现的位置在 $x_i$ 位置上，1-n的每个数都出现n次。

solution：

贪心。先将数组x按从小到大排序，然后先在 $x_i$ 位置上放上原来的下标的那个数，然后再从vis数组中从前往后枚举，放入相应数字（而不能从 $x_i$ 往前枚举，因为这样前面就可能出现空位，后面的数就不能放了），枚举完所有的x后。然后类似的贪心枚举后面的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int n;
struct node
{
   
    int x,id;
    bool operator <(const node pp)const
    {
   
        return x<pp.x;
    }
}p[505];
int vis[300005];
int main()
{
   
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
   
        scanf("%d",&p[i].x);
        p[i].id=i;
    }
    sort(p+1,p+1+n);
    memset(vis,0,sizeof(vis));
    bool flag=true;
    for(int i=1;i<=n;i++)
    {
   
        int pos=p[i].x;
        int c=p[i].id-1;
        if(vis[pos])flag=false;
        vis[pos]=p[i].id;
        pos=1;
        while(pos<p[i].x)
        {
   
            if(c==0)break;
            if(vis[pos]){
   pos++;continue;}
            vis[pos++]=p[i].id;
            c--;
        }
        if(c>0){
   flag=false;break;}
    }
    for(int i=1;i<=n;i++)
    {
   
        int pos=p[i].x+1;
        int c=n-p[i].id;
        while(pos<=n*n)
        {
   
            if(c==0)break;
            if(vis[pos]){
   pos++;continue;}
            vis[pos++]=p[i].id;
            c--;
        }
        if(c>0){
   flag=false;break;}
    }
    if(flag)
    {
   
        printf("Yes\n");
        for(int i=1;i<=n*n;i++)printf("%d ",vis[i]);
    }
    else printf("No");
    return 0;
}

题意：

给了一个字符串，你可以取出其中的一个字母的前提是，这个字符的两边还有字母，并且去掉这个字母后，断后重连的相邻两个字母不相同。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
string s;
int main()
{
   
    cin>>s;
    int n=s.length()-2;
    if(s[0]==s[s.length()-1])n--;
    if(n%2==0)printf("Second");
    else printf("First");
    return 0;
}

H-Cosmic Rays

题意：

给了起点和终点，以及n个圆圆心坐标和半径。问最短的从起点到终点的距离是多少（经过圆的那部分长度不算距离）。

solution:

另类的最短路。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int sx,sy,tx,ty,n;
struct node
{
   
    int x,y,id,r;
    double d;
    bool operator>(const node pp)const
    {
   
        return d>pp.d;
    }
}p[1005];
int vis[1005];
void dijktra()
{
   
    priority_queue<node,vector<node>,greater<node>>que;
    que.push(p[0]);
    while(!que.empty())
    {
   
        node tem=que.top();que.pop();
        if(vis[tem.id])continue;
        vis[tem.id]=1;
        for(int i=1;i<=n;i++)
        {
   
            if(i==tem.id)continue;
            double dis=sqrt(1ll*(tem.x-p[i].x)*(tem.x-p[i].x)+1ll*(tem.y-p[i].y)*(tem.y-p[i].y));
            if(dis>p[i].r+tem.r&&tem.d+dis-p[i].r-tem.r<p[i].d)
            {
   
                p[i].d=tem.d+dis-p[i].r-tem.r;
                que.push(p[i]);
            }
            else if(dis<=p[i].r+tem.r&&tem.d<p[i].d)
            {
   
                p[i].d=tem.d;
                que.push(p[i]);
            }
        }
    }
}
int main()
{
   
    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
    scanf("%d",&n);
    p[0].x=sx;p[0].y=sy;p[0].d=0;p[0].id=0;p[0].r=0;
    for(int i=1;i<=n;i++)
    {
   
        scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].r);
        p[i].id=i;
        p[i].d=1e18;
    }
    n++;
    p[n].x=tx;p[n].y=ty;p[n].id=n;p[n].d=1e18;p[n].r=0;
    dijktra();
    printf("%.10f",p[n].d);
    return 0;
}

I-Rotated Palindromes

J-Connectivity

题意：

给了你n个城市，k条路，l条高铁，问每个城市与几个城市是可达的（既要有路，又要有高铁），自己与自己也是可达的。

solution：

先分别对高铁和路进行并查集，然后寻找同一个点在哪两个集合，进行hash设置唯一标识，记录数量，只有标识相同代表这个城市与其他的标识相同的城市之间是可达的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int n,k,l;
int f[200005],f1[200005];
ll ha=3e5;
map<ll,int>mp;
int Find(int fa[],int x){
   return fa[x]==x?x:fa[x]=Find(fa,fa[x]);}
void Union(int fa[],int x,int y)
{
   
    x=Find(fa,x);
    y=Find(fa,y);
    fa[x]=y;
}
int main()
{
   
    scanf("%d%d%d",&n,&k,&l);
    for(int i=1;i<=n;i++)f[i]=f1[i]=i;
    for(int i=0;i<k;i++)
    {
   
        int u,v;scanf("%d%d",&u,&v);
        Union(f,u,v);
    }
    for(int i=0;i<l;i++)
    {
   
        int u,v;scanf("%d%d",&u,&v);
        Union(f1,u,v);
    }
    for(int i=1;i<=n;i++)
        mp[1ll*ha*Find(f,i)+Find(f1,i)]++;
    for(int i=1;i<=n;i++)
        printf("%d ",mp[1ll*ha*Find(f,i)+Find(f1,i)]);
    return 0;
}