[2023 CCPC 哈尔滨](The 2nd Universal Cup. Stage 10: Harbin - Dashboard - Contest - Universal Cup Judging System (ucup.ac)) BLM
B.Memory
思路：由递推式：\(Mood(i) = \sum_{j =1}^{i}2^{j-i}\times a_j\)可知,\(f[i] = f[i-1]/2+a[i]\)
显然直接\(/2\)会有精度问题啦，怎么办嘞。考虑把数分为整数部分和小数部分，分类讨论：
- \(Mood(i)<0\)：
- 整数部分\(<0\)
- 整数部分\(=0\)且小数部分\(<0\)
- \(Mood(i)=0\)：整数部分\(=0\)并且没有小数部分
- \(Mood(i)>0\)：
- 整数部分\(>0\)
- 整数部分\(=0\)且小数部分\(>0\)
// 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;
}
以上是正解，但是发现\(python\)大数写居然可以暴力\(AC\)?神奇
L.Palm Island
题意：把数组\(a\)变成\(b\)。
只能通过以下两种操作：
- 把第一个移到最后
- 把第二个移到最后
且操作次数\(\le n^2\)
思路：考虑用\(map\)把\(a\)在\(b\)中的位置做一个映射，这样相当于是现在只需要把映射之后的数组\(c\)排序即可。
我们思考这两个操作到底是什么含义。
这样子移动，变成有序，让我们联想到冒泡排序：
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]);
}
一轮排好一个，又回到开头去比较。类比到我们这题的两个操作：
我们考虑一个指针\(cur\)一开始指在\(0\)位置(初始位置)
- 把第一个移到最后：等价于指针后移
- 把第二个移到最后：等价于交换\(cur\)和\(cur+1\)位置的值之后指针后移
所以我们只需要按照冒泡排序的思想去写就行了。
// 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
题意：三种操作：画圆、画长方形、打印。输出打印的图
思路：这题我们发现，虽然坐标的数据范围很大但是打印出来的部分面积很小只有\(1e4\)，那直接离线然后暴力做就行了。
本题难点在于坐标的映射，两个坐标系的转换要小心。(debug了好久QAQ)
坐标映射应该是下面酱紫滴：
也就是原坐标的\((-5,5)\)对应我们的\((1,1)\)以此类推。
// 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;
}