2023 CCPC 哈尔滨 BLM

[2023 CCPC 哈尔滨](The 2nd Universal Cup. Stage 10: Harbin - Dashboard - Contest - Universal Cup Judging System (ucup.ac) ) BLM

B.Memory

思路：由递推式：可知,

显然直接会有精度问题啦，怎么办嘞。考虑把数分为整数部分和小数部分，分类讨论：

• ：
  1. 整数部分
  2. 整数部分且小数部分
• ：整数部分并且没有小数部分
• ：
  1. 整数部分
  2. 整数部分且小数部分

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n; cin>>n;
    ll x = 0,dec = 0;
    string ans = "";
    for(int i = 1;i <= n; i++)
    {
        ll y; cin>>y;
        x += y;
        if(x)
            ans += (x>0?"+":"-");
        else{
            if(dec)
                ans += (dec>0?"+":"-");
            else ans += "0";
        }

        if(x%2)
            dec = (x>0?1:-1);
        x/=2;
    }

    cout<<ans<<"\n";

    return 0;
}

以上是正解，但是发现大数写居然可以暴力?神奇

L.Palm Island

题意：把数组变成。

只能通过以下两种操作：

• 把第一个移到最后
• 把第二个移到最后

且操作次数

思路：考虑用把在中的位置做一个映射，这样相当于是现在只需要把映射之后的数组排序即可。

我们思考这两个操作到底是什么含义。

这样子移动，变成有序，让我们联想到冒泡排序：

void bubble_sort(int arr[], int len)  
{  
    int i, j;  
    for (i = 0; i < len; i++)  
        for (j = 1; j < len - i; j++)  
            if (arr[j - 1] > arr[j])  
                swap(arr[j - 1], arr[j]);  
}

一轮排好一个，又回到开头去比较。类比到我们这题的两个操作：

我们考虑一个指针一开始指在位置(初始位置)

• 把第一个移到最后：等价于指针后移
• 把第二个移到最后：等价于交换和位置的值之后指针后移

所以我们只需要按照冒泡排序的思想去写就行了。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N],b[N],c[N];
int mp[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;
        int cur = 0;
        for(int i = 0;i < n; i++)
            cin>>a[i];
        for(int i = 0;i < n; i++)
            cin>>b[i],mp[b[i]] = i;
        for(int i = 0;i < n; i++)
            c[i] = mp[a[i]];

        string ans = "";
        while(1)
        {
            if(cur == 0){
                int ok = 1;
                for(int i = 0;i < n-1; i++)
                    ok &= c[i]<c[i+1];
                if(ok)
                    break;
            }
            if(cur < n-1 && c[cur] > c[cur + 1]){
                swap(c[cur],c[cur+1]);
                cur++;
                ans += "2";
            }else{
                ans += "1";
                cur++;
            }
            cur %= n;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

M.Painter

题意：三种操作：画圆、画长方形、打印。输出打印的图

思路：这题我们发现，虽然坐标的数据范围很大但是打印出来的部分面积很小只有，那直接离线然后暴力做就行了。

本题难点在于坐标的映射，两个坐标系的转换要小心。(debug了好久QAQ)

坐标映射应该是下面酱紫滴：


也就是原坐标的对应我们的以此类推。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
vector<array<ll,6>>event;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n; cin>>n;
    for(int i = 1;i <= n; i++)
    {
        string ty; cin>>ty;
        if(ty == "Circle"){
            ll x,y,r;
            char col;  cin>>x>>y>>r>>col;
            event.push_back({1,x,y,r,(ll)col,0});
        }else if(ty == "Rectangle"){
            ll x1,y1,x2,y2;
            char col;  cin>>x1>>y1>>x2>>y2>>col;
            event.push_back({2,x1,y1,x2,y2,(ll)col});
        }else if(ty == "Render"){
            ll x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;
            event.push_back({3,x1,y1,x2,y2,0});
        }
    }


    for(int i = 0;i < n; i++)
    {
        int op = event[i][0];
        // cout<<"op = "<<op<<'\n';
        if(op == 3){
            ll x1 = event[i][1],y1 = event[i][2];
            ll x2 = event[i][3],y2 = event[i][4];

            ll h = y2-y1+1, w = x2-x1+1;
            char a[h+10][w+10];
            memset(a,0,sizeof(a));
            for(int j = 0;j <= h; j++)
                for(int k = 0;k <= w; k++)
                    a[j][k] = '.';
            ll idx[h+10],idy[w+10];
            memset(idx,0,sizeof(idx));
            memset(idy,0,sizeof(idy));
            ll t = y2;
            for(int j = 1;j <= h; j++)
                idx[j] = t,t--;
            t = x1;
            for(int j = 1;j <= w; j++)
                idy[j] = t,t++;

            // cout<<"debug:__________________________\n";
            //  for(int j = 1;j <= h; j++)
            //     cout<<idx[j]<<" ";
            // cout<<"\n";
    
            // for(int j = 1;j <= w; j++)
            //      cout<<idy[j]<<" ";
            // cout<<"\n";

            // for(int i = 1;i <= h; i++)
            // {
            //     for(int j = 1;j <= w; j++)
            //     {
            //         cout<<"("<<idy[j]<<","<<idx[i]<<")";
            //     }
            //     cout<<"\n";
            // }

            for(int j = 0;j < i; j++)
            {
                op = event[j][0];
                if(op==1){
                    ll u = event[j][1],v = event[j][2],r = event[j][3],col = event[j][4];
                    //cout<<"u = "<<u<<" v = "<<v<<"\n";
                    for(int k = 1;k <= h; k++)
                        for(int l = 1;l <= w; l++){

                        //cout<<"idx[k] = "<<idx[k]<<" idy[l] = "<<idy[l]<<"\n";
                        if((u-idy[l])*(u-idy[l])+(v-idx[k])*(v-idx[k])<=r*r)
                            a[k][l] = char(col);
                        }
                            
                        
                }else if(op==2){
                    ll x1 = event[j][1],y1 = event[j][2];
                    ll x2 = event[j][3],y2 = event[j][4];
                    ll col = event[j][5];

                     for(int k = 1;k <= h; k++)
                        for(int l = 1;l <= w; l++)if(x1<=idy[l]&&idy[l]<=x2&&y1<=idx[k]&&idx[k]<=y2){
                            a[k][l] = char(col);
                        }
                }
            }

            for(int j = 1;j <= h; j++)
            {
                for(int k = 1;k <= w; k++)
                    cout<<a[j][k];
                cout<<"\n";
            }

        }
    }

    return 0;
}