比赛链接

传送门

C.Corrupted Contest

题意

输入一个n表示有n个人,然后输入一个p表示有p道题,接下来输入n行表示每个人昨晚最后一题的时间的排名,问你能否找到一种做题的排序方式使得满足这样的时间排序,如果存在不能确定的情况就输出"ambiguous",否则输出每个人的做题数

解题思路

很明显这个题目是非递增的序列,并且如果后一个人的最后做出来的时间比前面一个人少的话,那么后一个人的做题的数量必然比前面那个人的做题数目少, 但是需要注意的是如果遇到时间为0的情况那么这个人做出来的题目数必然为0,我们通过差分处理一下,如果第一个时间为0的话后面都是0,直接输出就行,否则的话第一个人的做题数一定是p,然后我们按照之前的差分数组遇到-1就减少,我们最后再扫一遍结果数组,如果出现断层情况那么一定是不能确定的,那么找到了断层就直接输出"ambiguous"否则的话就直接输出我们处理的答案

Code

#include
using namespace std;
const int N = 10005; 
int n,p,a[N],b[N],c[N];


int main()
{
    scanf("%d%d",&n,&p);
    for(int i = 0;i < n; ++i) {
        scanf("%d",&a[i]);
    }
    memset(c,-1,sizeof c);
    if(a[0]) {
        c[0] = p;
    }
    else {
        c[0] = 0;
    }
    c[n] = 0;
    for(int i = 1;i < n; ++i) {
        if(a[i] == 0) {
            c[i] = 0;
            continue;
        }
        if(a[i]-a[i-1] >= 0) {
            b[i] = 1;
        }
        else {
            b[i] = -1;
        }
    }
    for(int i = 1;i < n; ++i) {
        if(c[i] == 0) continue;
        if(b[i] == 1) {
            c[i] = c[i - 1];
        }
        else {
            c[i] = c[i - 1] - 1;
        }
    }
    for(int i = 1;i <= n; ++i) {
        if(c[i] - c[i-1] < -1) {
            puts("ambiguous");
            return 0;
        }
    }
    for(int i = 0;i < n; ++i) {
//      printf("c[%d] = %d\n",i + 1,c[i]);
        printf("%d\n",c[i]);    
    }

    return 0;
}

E.Efficiently Elevated

题意

给你一个h \times w 的地图,然后给每个坐标点输入一个值,表示的是该点楼层的高度,高度为1的楼层不需要电梯,在一个楼层群中只需要建立一个最高的楼层的电梯即可,问你最少需要多少电梯

解题思路

很明显我们可以优先对楼层高的电梯周围的较低楼层进行染色,然后看染色几次就能全部满足,这个就是最少所需要的电梯数

Code

#include
using namespace std;

const int N = 505;
int n,m;
int mp[N][N];
int A[N][N];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

struct node {
    int x,y,h;
    node(int x,int y,int h) {
    this->x = x;
    this->y = y;
    this->h = h; 
    }
    bool operator< (const node &r) const { return (h < r.h); }
};

void dfs(int i,int j) {
    if(!mp[i][j]) return;
    mp[i][j] = 0;
    for(int k = 0;k < 4; ++k) {
        int nx = i + dx[k];
        int ny = j + dy[k];
        if(nx > 0 && nx <= n && ny > 0 && ny <= m && A[i][j] >= A[nx][ny]) {
            dfs(nx,ny);
        } 
    }
}
priority_queue que;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n; ++i) {
        for(int j = 1;j <= m; ++j) {
            scanf("%d",&mp[i][j]);
            A[i][j] = mp[i][j];
            if(mp[i][j] <= 1)
                mp[i][j] = 0;
            else 
                mp[i][j] = 1;
            que.push({i,j,A[i][j]});
        }
    }
    int ans = 0;
    while(que.size()) {
        node p = que.top();
        que.pop();
        if(mp[p.x][p.y]) {
            dfs(p.x,p.y);
            ans++;
        }
    }
    printf("%d",ans);

    return 0;
}

H.Hungry Henk

题意

输入一个n,表示有n组菜,然后对每一组菜输入一个d表示的是每一组菜有多少个菜,然后输入d个菜,问你能否找到一组菜,它的每一个菜的小写字母个数都小于等于20,然后输出这一组菜(可以输出任意满足题意的答案)

解题思路

直接暴力模拟就行,签到题

Code

#include
using namespace std;
int n;
int main()
{
    int d;
    string ch,ans="";
    int ansd;
    cin>>n;

    for(int i = 0;i < n; ++i) {
        cin>>d;
        ansd = d;
        bool fg = true;
        for(int j = 0;j < d; ++j) {
            cin>>ch;
            if(ch.size() > 20) fg = false;
            ans += ch;
            ans += "\n";
        }
        if(fg == true) {
            while(++ i < n) {
                cin>>d;
                for(int j = 0;j < d; ++j) 
                    cin>>ch;
            }
            cout<

I.Incomplete Implementation

题意

输入长度为n的乱序数组(每个数都是不一样的,但是都是小于等于n的),然后你可以每次任意选择n/2个不同的下标使得他们值排序,然后有序放回这几个位置,你最多有三次操作机请问你怎么操作,会使得这个乱序数组恢复有序。(可以输出仍以方式)

解题思路

我们第一步先让 [1,n/2] 的值恢复到原位,然后再让[n/4+1,n/2]恢复到原位,最后直接输出剩下的n/2个数,即可完成排序,值得注意的是,当我们再处理前两种的情况有可能会有这样的情况,那个数本来就在自己的位置,那么我们就需要找一些其他位置的数来凑成n/2个数,我们应该从1开始往后选择,因为我们是优先对前面处理,也就是前面的数字不会影响我们对排序的处理

Code

#include
using namespace std;

const int N = 100005;

int n,a[N],b[N];
set ans;

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n; ++i) {
        scanf("%d",&a[i]);
        b[a[i]] = i;
    }
    printf("%d\n",3);
    ans.clear();
    for(int i = 1;i <= n/4; ++i) {
        int a1 = b[i];
        int a2 = i;
        if(a1 == a2) {
            a2 = n;
        }
        else {
            b[a[i]] = a1; 
            b[i] = i;

            int temp = a[a1];
            a[a1] = a[a2];
            a[a2] = temp;
        }
        ans.insert(a1);
        ans.insert(a2);
    }
    int i = 1;
    while(ans.size() < n / 2) {
        ans.insert(i++);
    }
    for(auto it : ans) {
        printf("%d ",it);
    }
    puts("");
    ans.clear();
//  for(int i = 1;i <= n; ++i) printf("%d%c",a[i],i==n?'\n':' ');
//  for(int i = 1;i <= n; ++i) printf("%d%c",b[i],i==n?'\n':' ');
//  for(int i = 1;i <= n; ++i) b[a[i]] = i;
    for(int i = n/4 + 1;i <= n/2; ++i) {
        int a1 = b[i];
        int a2 = i;
        if(a1 == a2) {
            a2 = n;
        }
        else {
            b[a[i]] = a1; 
            b[i] = i;

            int temp = a[a1];
            a[a1] = a[a2];
            a[a2] = temp;
        }
        ans.insert(a1);
        ans.insert(a2);
    }
    i = 1;
    while(ans.size() < n / 2) {
        ans.insert(i++);
    }
    for(auto it : ans) {
        printf("%d ",it);
    }
    puts("");
//  for(int i = 1;i <= n; ++i) b[a[i]] = i;
    for(int i = n/2+1;i <= n; ++i) {
        printf("%d%c",a[i],i==n?'\n':' ');
    }
//  for(int i = 1;i <= n; ++i) {
//      printf("%d ",a[i]);
//  }
    return 0;
}

J.Jigsaw

题意

给你拼图的一些碎片,角落的碎片数为c,边缘的碎片数为e,中间的碎片数为m,问你能否用尽这些碎片拼出一个图,如果可以的话就输出最后拼图的长和宽,否则输出“impossible”

解题思路

很明显如果角落的c不为4,那么一定不能满足条件,然后如果e不能被2整除那么一定不能满足条件,最后就是计算长和宽了,这里我们设内矩形的长和宽为a,b

(a + b)\times 2= e

a\times b = m

然后可以得到一个一元二次方程,注意的是,解可能有两种,所以我们两种都要考虑

Code

#include
using namespace std;
#define int long long
int c,e,m;
signed main()
{
    cin>>c>>e>>m;
    if(c == 4) {
        if(e % 2 == 0) {
            int a1,a2,b1,b2;
            a1 = (e + sqrt((e*e-16.0*m)))/4.0;
            a2 = (e - sqrt((e*e-16.0*m)))/4.0;
            b1 = (e/2)-a1;
            b2 = (e/2)-a2;
            if(a1 * b1 == m) {
                printf("%lld %lld\n",a1+2,b1+2);
            }
            else if(a2 * b2 == m) {
                printf("%lld %lld\n",a2+2,b2+2);
            }
            else {
                puts("impossible");
            }
        }
        else {
            puts("impossible");
        }
    }
    else {
        puts("impossible");
    }
    return 0;
 } 

感想

被各位大佬暴捶……
这个绝望小学我可能一被子都忘不掉(

打下来除了E题一直读错题,rhr写了一发wa了,然后我按照他的理解写了一发然后又wa了,然后我又去读题,感觉还是没懂,结果比赛结束发现是真的读错题了,想起了yy在比赛的时候想了个反例我按照rhr的想法,就直接否定了……,然后最后半小时就一直挂机


本当の声を響かせてよ