20241008

其实国庆期间写的，但是没整理。

B. Party

题意

有 \(n\) 个人，\(m\) 对朋友关系。举办聚会，邀请若干人，使得被邀请的人中，是朋友关系的有偶数对。每个人有个开心值\(a[i]\)，如果第 \(i\) 个人没有被邀请，会获得\(a[i]\)的不开心值。问怎么邀请，使总得不开心值最小。

思路

在是偶数对朋友关系的情况下，尽可能多邀请人。那么我们一开始邀请全部人，对 \(m\) 进行奇偶讨论即可。

• 偶数：不用删去。
• 奇数：删去一对朋友关系：有两种情况：
  • 如果删去的点度为奇数，只需要删去一个
  • 否则删去它本身，以及与它相连的一个顶点。

代码

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
const int MAXN=5e5+10;
void solve()
{
    int n, m;   cin >> n >> m;
    std::vector<int> a(n);
    std::vector<int> deg(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    std::vector<int> u(m), v(m);
    for (int i = 0; i < m; ++i)
    {
        cin >> u[i] >> v[i];
        u[i]--, v[i]--;
        deg[u[i]]++;
        deg[v[i]]++;
    }
    int ans = 1e9;
    if(m % 2 == 0)
    {
        cout << 0 <<"\n";
        return;
    }
    for (int i = 0; i < n; ++i)
    {
        if(deg[i] & 1)  ans = min(ans, a[i]);
    }
    for (int i = 0; i < m; ++i)
    {
        if(deg[u[i]] % 2 == 0 && deg[v[i]] % 2 == 0)
        {
            ans = min(ans, a[u[i]] + a[v[i]]);
        }
    }
    cout << ans << "\n";
} 
int main(){
    int t=1;
    cin >> t;
    for (int i = 0; i < t; ++i)
    {
        //cerr<<"case "<<i<<": ";
        solve();
    }
} 

C. Color the Picture

思路

看样例比较容易发现思路：每次最少填充两行或者两列。我们可以贪心的选取颜料较多的进行填充。

代码

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
const int MAXN=5e5+10;
void solve()
{
    i64 n, m, k;    std::cin >> n >> m >> k;
    std::vector<i64> a(k);
    for (int i = 0; i < k; ++i)
    {
        std::cin >> a[i];
    }
    sort(begin(a), end(a), greater<int>());
    //先按照列进行染色
    bool ok = false;
    i64 res = 0, leave = 0;
    for (int i = 0; i < k; ++i)
    {
        i64 cal = a[i] / n;				//可以填充的列数
        cal = min (cal, m - res);		//计算需要填充的数目		
        if(cal < 2) continue;			
        res += 2;						//现在至少可以填充两列
        leave += cal - 2;				//剩下可以填充的
    }
    ok |= (res + leave >= m);			//能否全部填充完毕

    swap(n, m);							//一样的处理
    res = 0, leave = 0;
    for (int i = 0; i < k; ++i)
    {
        i64 cal = a[i] / n;
        cal = min (cal, m - res);
        if(cal < 2) continue;
        res += 2;
        leave += cal - 2;
    }
    ok |= (res + leave >= m); 
    cout << (ok ? "YES" : "NO") << "\n";
} 
int main(){
    int t=1;
    cin >> t;
    for (int i = 0; i < t; ++i)
    {
        //cerr<<"case "<<i<<": ";
        solve();
    }
} 

B. Luke is a Foodie

思路

从左到右，模拟去取每个食物可以接受美味度的左右边界。

• 如果吃不了的，就只能新开一个v，次数+1。
• 如果吃得了的，则更新，当前食物集合的左右边界的交集。

代码

Code1

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
const int MAXN=5e5+10;
void solve()
{
    int n;  std::cin >> n;
    i64 x;  std::cin >> x;
    std::vector<i64> a(n), l(n), r(n);
    for (int i = 0; i < n; ++i)
    {
        std::cin >> a[i];
        l[i] = a[i] - x;
        r[i] = a[i] + x;
    }
    int ans = 0;
    i64 low = l[0], high = r[0];
    for (int i = 1; i < n; ++i)
    {
        if(high >= l[i] && low <= l[i])
        {
            low = max(low, l[i]);
            high = min(high, r[i]);
        }
        else if(low <= r[i] && high >= r[i])
        {
            low = max(low, l[i]);
            high = min(high, r[i]);
        }
        else if(low >= l[i] && high <= r[i])    continue;
        else
        {
            ans++;
            low = l[i];
            high = r[i];
        }
    }
    std::cout << ans <<"\n";
} 
int main(){
    int t=1;
    cin >> t;
    for (int i = 0; i < t; ++i)
    {
        //cerr<<"case "<<i<<": ";
        solve();
    }
} 

Code2

#include<bits/stdc++.h>
#define lowbit(x) x & (-x)
using namespace std;
using i64=long long;
const int MAXN=1e5+10;
void solve()
{
    int n, x;   cin >> n >> x;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    int l = a[0] - x, r = a[0] + x;
    int ans = 0;
    for (int i = 1; i < n ; ++i)
    {
        if(r < a[i] - x || a[i] + x < l)
        {
            ans++;
            l = a[i] - x;
            r = a[i] + x;
        }
        else
        {
            l = max(l, a[i] - x);
            r = min(r, a[i] + x);
            //continue;
        }
    }
    cout << ans << "\n";
} 
int main(){
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i)
    {
        //cerr<<"case "<<i<<": ";
        solve();
    }
} 

C. Build Permutation

思路

这里先引入一个定理：对于任意的非负数 \(n\)，区间 $[n,2n] $至少存在一个完全平方数。

证明：

当 \(n= 1,2,3,4\)时，完全平方数为\(0,1,4,4,4\)。

当\(n \geq 5\)：因为\(\lceil \sqrt{n} \rceil \leq \sqrt{n} + 1\)，有： \[ (\lceil \sqrt{n} \rceil)^2 \leq n + 2\sqrt{n} +1 \] 又因为： \[ n - 2\sqrt{n} - 1 = (\sqrt{n} - 1)^2 -2 \geq (\sqrt{5}-1)^2 > 0 \] 所以可以得到： \[ n \leq (\lceil n \rceil )^2 \leq n + 2\sqrt{n} + 1\leq 2 \times n \] 故区间\([n, 2n]\)中存在\((\lceil \sqrt{n}\rceil)^2\)，同理可以构造出\((\lceil \sqrt{2n}\rceil)^2\)。

那么我们可以进行先计算出\(h=(\lceil \sqrt{2n}\rceil)^2\)，然后对于这个区间\([h-n, h]\)内的每一项进行构造。

类似的进行递归构造，处理\(h-n-1\)。

这里提一嘴为什么会是构造：\(h=(\lceil \sqrt{2n}\rceil)^2\)，因为最大就是\(n + n =2n\)。所以是这样构造。

代码

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
const int MAXN=5e5+10;
void solve()
{
    int n;  cin >> n;
    std::vector<int> ans(n+1);
    auto f = [&](auto f, int r) -> void
    {
        if(r < 0)   return;
        int num = sqrt(2 * r); num *= num;	
        int l = num - r;	//注意一下l和r是互补对称的
        f(f, l - 1);
        for (; l <= r; ++l, --r)
        {
            ans[l] = r;
            ans[r] = l;
        }
    };
    f(f, n - 1);
    for (int i = 0; i < n; ++i)
    {
        cout << ans[i] <<" \n"[i==n-1];
    }
} 
int main(){
    int t=1;
    cin >> t;
    for (int i = 0; i < t; ++i)
    {
        //cerr<<"case "<<i<<": ";
        solve();
    }
}