Educational Codeforces Round 124 (Rated for Div. 2) (D 边缘点bfs推答案 C贪心)

A：第一轮剩下的都是奇数，后面全是奇数了，说明两个数相加永远都是偶数，最后答案是最大的那个奇数

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int x[N],y[N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void solve()
{
    cin>>n;
    cout<<(1<<n)-1<<"\n";
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
   
    cin>>t;
    while(t--) solve();
}

B：

推公式

2*|x-y|>=x+y

设x>=y

2*x-2*y>=x+y

x>=3*y

所以大的那个数至少要大于等于前面的数3倍

由于要n最多项，所以第一个数从1开始，且增长三倍

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
int f[N];
void solve()
{
    cin>>n;
    
    for(int i=1,j=1;i<=n;i++,j*=3){
        if(j>1e9){
            cout<<"NO\n";return ;
        }
        a[i]=j;
    }
    cout<<"YES\n";
    for(int i=1;i<=n;i++)
    cout<<a[i]<<" \n"[i==n];
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
   
    cin>>t;
    while(t--) solve();
}

C：

例子a= 1 1 1 1?

? ? ? ?b=1 1 1 1

假设去掉第一个a

那么[ ] 和[2,4]两个区间都要从里面选一个连b

去掉第二个a

[1]? 和 [3,4]

去掉第三个a

[1,2] 和[4]

去掉第四个

[1,2,3] 和[]

观察到第一个点和最后一个点都一定要连

所以直接枚举就行

#include <bits/stdc++.h>
using namespace std;
long long t, n, a[200010], b[200010], ans, ta1, tam, tb1, tbn;
int main() {
	ios::sync_with_stdio(0);
	cin >> t;
	while(t--) {
		cin >> n;
		for(int i = 1; i <= n; i++) cin >> a[i];
		for(int i = 1; i <= n; i++) cin >> b[i];
		ta1 = tam = tb1 = tbn = 4e18;
		for(int i = 1; i <= n; i++) ta1 = min(ta1, abs(a[1] - b[i]));
		for(int i = 1; i <= n; i++) tam = min(tam, abs(a[n] - b[i]));
		for(int i = 1; i <= n; i++) tb1 = min(tb1, abs(a[i] - b[1]));
		for(int i = 1; i <= n; i++) tbn = min(tbn, abs(a[i] - b[n]));
		ans = min(abs(a[1] - b[1]) + abs(a[n] - b[n]), abs(a[1] - b[n]) + abs(a[n] - b[1]));
		ans = min(ans, min(abs(a[1] - b[1]) + tam + tbn, abs(a[n] - b[n]) + ta1 + tb1));
		ans = min(ans, min(abs(a[1] - b[n]) + tam + tb1, abs(a[n] - b[1]) + ta1 + tbn));
		ans = min(ans, ta1 + tb1 + tam + tbn);
		cout << ans << endl;
	}
	return 0;
}

D：

因为最多200000个点,最近的点，一定是红色点边缘点

边缘点最多就1e6个点，所以直接从边缘点向红色点进行bfs即可

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int x[N],y[N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void solve()
{
    cin>>n;
    map<PII,int> mp;
    queue<node> q;
    set<PII> st;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        mp[{x[i],y[i]}]=i;
        for(int j=0;j<4;j++){
            int tx=x[i]+dx[j],ty=y[i]+dy[j];
            st.insert({tx,ty});
        }
    }
    map<PII,PII> res;
    for(auto [x,y]:st){
        if(mp.count({x,y})) continue;
        q.emplace(x,y,x,y);
    }
    set<PII> v;
    while(q.size())
    {
        auto [lx,ly,x,y]=q.front();
        q.pop();
        if(v.count({x,y})) continue;
        v.insert({x,y});
        for(int i=0;i<4;i++){
            int tx=x+dx[i],ty=y+dy[i];
            if(!mp.count({tx,ty})) continue;
            if(!res.count({tx,ty}))
            {
                res[{tx,ty}]={lx,ly};
            }
            q.emplace(lx,ly,tx,ty);
        }
    }
    for(int i=1;i<=n;i++) cout<<res[{x[i],y[i]}].first<<" "<<res[{x[i],y[i]}].second<<"\n";
    
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
   
   // cin>>t;
    while(t--) solve();
}