Codeforces Round #703 (Div. 2) (A~E)

2021 年 2 月 19 日
筆記
Codeforces, 二分, 思維, 最短路, 貪心

A. Shifting Stacks

題目鏈接

點我跳轉

題目大意

給定 $N$ 個土堆，第 $i$ 個土堆有 $Ai$ 個木塊

你可以將第 $i$ 個土堆的木塊轉移至第 $i + 1$ 個土堆

問能否使土堆的木塊數量構成上升序列

解題思路

貪心

最優的構造方法即令土堆的木塊數一次為 $0 , 1 , 2 , 3 … $

定義 $sum[i]$ 為 $ai$ 的前綴和，那麼只要判斷是否每個前綴和都滿足 $sum[i] >= (i – 1) × i / 2$

AC_Code

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e2 + 10;

int n , a[N] , sum[N];

signed main()
{
	int T = 1;
	
	cin >> T;
	
	while(T --)
	{
		cin >> n;
		
		for(int i = 1 ; i <= n ; i ++) cin >> a[i] , sum[i] = sum[i - 1] + a[i];
	
		bool ok = true;
	
		for(int i = 1 ; i <= n ; i ++)
		{
			if(sum[i] - (i - 1) * i / 2 < 0) {
				ok = false ; break ;
			}
		}
		
		if(ok) cout << "YES\n";
		
		else cout << "NO\n";
	}
	
	return 0;
}#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e2 + 10;

int n , a[N] , sum[N];

signed main()
{
	int T = 1;
	
	cin >> T;
	
	while(T --)
	{
		cin >> n;
		
		for(int i = 1 ; i <= n ; i ++) cin >> a[i] , sum[i] = sum[i - 1] + a[i];
	
		bool ok = true;
	
		for(int i = 1 ; i <= n ; i ++)
		{
			if(sum[i] - (i - 1) * i / 2 < 0) {
				ok = false ; break ;
			}
		}
		
		if(ok) cout << "YES\n";
		
		else cout << "NO\n";
	}
	
	return 0;
}

B. Eastern Exhibition

題目鏈接

點我跳轉

題目大意

二維平面上給定 $n$ 個點，問存在多少個整數坐標點使得這些點到 $n$ 個點的曼哈頓距離總和最小

解題思路

如果是一維直線，那麼這些點只會存在於橫坐標 $x$ 的中位數之間，或者縱坐標 $y$ 的中位數之間

那麼滿足條件的點個數即為橫坐標 $x$ 的中位數之間的長度或縱坐標 $y$ 的中位數之間的長度

拓展到二維這些點的個數即為橫坐標 $x$ 的中位數之間的長度 $×$ 縱坐標 $y$ 的中位數之間的長度

當 $n$ 為奇數時，$x$ 的中位數只有 $1$ 個，$y$ 的中位數只有 $1$ 個，所以答案為 $1$

當 $n$ 為偶數時，答案即是 $x$ 的中位數之間的長度 $×$ $y$ 的中位數之間的長度

AC_Code

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e3 + 10;

int n , x[N] , y[N];

signed main()
{
	int T = 1;
	
	cin >> T;
	
	while(T --)
	{
		cin >> n;
		
		for(int i = 1 ; i <= n ; i ++) cin >> x[i] >> y[i];
		
		sort(x + 1 , x + 1 + n) , sort(y + 1 , y + 1 + n);
		
		if(n & 1) cout << 1 << '\n';
		
		else cout << (x[n / 2 + 1] - x[n / 2] + 1) * (y[n / 2 + 1] - y[n / 2] + 1) << '\n';
	}
	
	return 0;
}

C1&C2.Guessing the Greatest

題目鏈接

點我跳轉

題目大意

交互問題

有一個序列，每次你可以詢問區間 $[L , R]$ 的次大值的位置

要求在 $20$ 次詢問內找出最大值的位置

解題思路

對於區間 $[L , R]$ 的次大值位置為 $pos$

那麼最大值必然只出現在區間 $[L , pos – 1]$ 或區間 $[pos + 1 , R]$

於是可以再次詢問區間 $[L , pos]$ 的次大值位置判斷最大值是位於區間 $[L , pos-1]$ 還是區間 $[pos +1 , R]$

當 $query([L , pos]) = pos$ , 且 $pos != 1$ 時，最大值處於區間 $[L , pos – 1]$

此時可以令 $R = pos – 1$ , 並二分最大值的位置 $mid$

如果 $query([mid , pos]) = pos$ ，則可以確定最大值位於區間 $[mid , pos]$ , 於是捨棄 $[l , mid – 1]$

否則可以確定最大值不位於區間 $[mid , pos]$ , 於是二分的區間改為 $[l , mid – 1]$

否則最大值位於區間 $[pos +1 , R]$ , 操作大致同上

AC_Code

#include<bits/stdc++.h> 

using namespace std;

int n , x;

int query(int l , int r)
{
	cout << "? " << l << " " << r << '\n';	
	
	cin >> x;
	
	return x;
}
signed main()
{
	
	cin >> n;
	
	int l = 1 , r = n , res = 0;
	
	int pos = query(1 , n);
	
	if(pos != 1 && query(1 , pos) == pos)
	{
		l = 1 , r = pos - 1;
		
		while(l <= r)
		{
			int mid = l + r >> 1;
			 
			if(query(mid , pos) == pos) res = mid , l = mid + 1;
			
			else r = mid - 1;
		}
		
	}
	else
	{
		l = pos + 1 , r = n;
			
		while(l <= r)
		{
			int mid = l + r >> 1;
			
			if(query(pos , mid) == pos) res = mid , r = mid - 1;
			
			else l = mid + 1;
		}
	}
	
	cout << "! " << res << '\n';
	
	return 0;
}

D. Max Median

題目鏈接

點我跳轉

題目大意

給定一個序列，要求選出一個長度大於等於 $k$ 的連續子序列

使得該序列的中位數最大

問最大中位數是多少？

解題思路

二分中位數 $x$

將序列中大於等於它的數變為 $1$ ，小於它的數變為 $0$

假設選出的序列長度 $len$ ，序列中 1 的個數為 $cnt$

那麼當 $cnt – 1 >= len / 2$ 時，返回 $true$

這裡解釋下兩個問題：

為什麼式子左邊是 $cnt – 1$ 而不是 $cnt$?

為什麼不是 $cnt – 1 = len / 2$ 而是 $cnt – 1 >= len / 2$

q1. $cnt – 1$ 是因為序列中的某個 $1$ 得作為 x 本身

q2. 因為當 $cnt – 1 > len / 2$ 時，必然存在一個大於 $x$ 的數滿足 $cnt – 1 = len / 2$，所以需要返回 $true$ 以向上改變二分區間

我們可以枚舉區間右端點，並選定左端點以使式子的結果為 $true$

定義 $sum[i]$ 為序列的前綴和，$L$ 為當前區間的左端點 $-1$ , $R$ 為當前區間的右端點

那麼 $cnt = sum[R] – sum[L]$ , $len = R – L$

於是式子可以轉變為 $sum[R] – sum[L] – 1 >= (R – L) / 2$

通過移項，式子可變為 $2 × sum[R] – R – 2 >= 2 × sum[L] – L$

因為 $R$ 是我們枚舉的 , 所以 $R、sum[R]$ 都可認為常數

為了讓不等式成立，我們需要讓不等號右邊的式子儘可能小

所以我們要取 $mi$ $=$ $min∑(2 * sum[i] – i) , i ∈[1 , i – k]$

因為每枚舉一個右端點，只會出現一個新的可以選擇的左端點 $i-k$

所以 $mi$ 對於每一個右端點只要 $O1$ 就可以得到了

注意：

得到了 $mi$ 我們不能直接改寫式子為 $2 × sum[R] – R – 2 >= mi$

因為 $(4 – 1) / 2 = 1$ 而不是 $1.5$

所以我們還要維護兩個變數分別代表 $sum[L]$ 和 $L$

AC_Code

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;

int n , m , k , a[N] , b[N] , sum[N];

bool check(int x)
{
	int mi = 1e9 , pre = 1e9 , pos = -1e9;

	for(int i = 1 ; i <= n ; i ++)
	{
		if(a[i] >= x) b[i] = 1;
		
		else b[i] = 0;
		
		sum[i] = sum[i - 1] + b[i];
		
		if(i - k >= 0 && mi >= 2 * sum[i - k] - (i - k))
		{
			mi = 2 * sum[i - k] - (i - k);
			pos = i - k;
			pre = sum[i - k];
		}
		
		if(sum[i] - pre - 1 >= (i - pos) / 2) return true;
	}
	return false;
}

signed main()
{	
	cin >> n >> k ;
	
	for(int i = 1 ; i <= n ; i ++) cin >> a[i];
	
	int l = 1 , r = n , res = 0;
	
	while(l <= r)
	{
		int mid = l + r >> 1;
		
		if(check(mid)) l = mid + 1 , res = mid;
		
		else r = mid - 1;
	}
	
	cout << res << '\n';
	
	return 0;
}

E. Paired Payment

題目鏈接

點我跳轉

題目大意

給定一張包含 $N$ 個點，$M$ 條邊的無向圖，每條邊都有它的權值 $w$ $(1 <= w <= 50)$

每次從一個節點出發，都必須走完兩條邊才能停下(中間經過的點不算到達過)

途中的花費為兩條邊權值的和的平方

問節點 $1$ 出發到達每個點所需的最小花費分別為多少

解題思路

很多人用暴力的做法居然沒有 $fst$ ？這就很神奇 $hhh$

update： 大數據貌似在 $fst$ 之後才加上

定義 $ans[i]$ 表示從節點 $1$ 出發到達節點 $i$ 的最小花費

定義 $dis[w][i]$ 表示從某個點 $x$ 走了 一條權值為 w 的邊 到達節點 $i$ ，而 $dis[w][i] = min(ans[x])$

假設當前節點為 $u$ , 它的相鄰節點為 $v$ , 它們之間的邊權為 $w$

那麼不難得到
dis[w][v] = min(dis[w][v] , ans[u]);
for(int j = 1 ; j <= 50 ; j ++) ans[v] = min(ans[v] , dis[j][u] + (j + w) * (j + w));
所以跑 $dijkstra$ 時只要邊權被更新我們就把該點入隊

但是傳統的 $dijkstra$ 在一個點入隊後就會被打上標記從此不能再入隊了

而這裡我們顯然是需要一個點重複入隊才能保證答案的最優

如果選擇重複入隊就會使得複雜度爆炸？那怎麼辦呢？

我們可以統計每個點入隊的次數，當次數大於 $50$ 時就不再入隊

這樣可行是因為 $dis$ 是由 $ans$ 更新 , $ans$ 是由 $ans$ 和邊權更新

而邊權最大只有 $50$ , $50$ 次入隊足夠讓 $ans$ 由所有的邊權更新一遍了

AC_Code

#include<bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

const int N = 2e5 + 10;

struct node{
    int dis , pos;
    bool operator <( const node &x )const{
        return x.dis < dis;
    }
};

struct Edge{
    int to , w , nex;
}edge[N << 1];

int head[N], dis[51][N] , tot , vis[N] , n , m , s , ans[N];

inline void add_edge(int u , int v , int d)
{
    edge[++ tot].w = d;
    
    edge[tot].to = v;
    
    edge[tot].nex = head[u];
    
    head[u] = tot;
}
inline void dijkstra(int s)
{
    for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j <= 50 ; j ++) ans[i] = dis[j][i] = inf;
	
    ans[s] = 0;
    
    priority_queue <node> que;
    
    que.push(node{0 , s});
    
    while(!que.empty())
    {
        node tmp = que.top();
        
        que.pop();
        
        int u = tmp.pos , d = tmp.dis ;
        
        if(vis[u] > 50) continue;
        
        vis[u] ++;
        
        for(int i = head[u] ; i ; i = edge[i].nex)
        {
            int v = edge[i].to , w = edge[i].w;
                  
            for(int j = 1 ; j <= 50 ; j ++)
            {
            	int cost = dis[j][u] + (j + w) * (j + w);
				
				if(cost < ans[v]) 
				{
					ans[v] = cost;
					
					if(vis[v] <= 50) que.push(node{ans[v] , v});
				}
			}
			
			if(dis[w][v] > ans[u]) 
            {
            	dis[w][v] = ans[u];
            	
            	if(vis[v] <= 50) que.push(node{dis[w][v] , v});
			}
        }
    }
}
signed main()
{
    cin >> n >> m;
 
    for(int i = 1 ; i <= m ; i ++)
    {
        int u , v , w;
 
        cin >> u >> v >> w;
 
        add_edge(u , v , w);
 
        add_edge(v , u , w);
    }
 
    dijkstra(1);
 	
 	for(int i = 1 ; i <= n ; i ++)
	{
		if(ans[i] == inf) ans[i] = -1;
		
		cout << ans[i] << " ";
	}
	
    return 0;
}

Tags: Codeforces 二分思維最短路貪心

Codeforces Round #703 (Div. 2) (A~E)

A. Shifting Stacks

題目鏈接

題目大意

解題思路

AC_Code

B. Eastern Exhibition

題目鏈接

題目大意

解題思路

AC_Code

C1&C2.Guessing the Greatest

題目鏈接

題目大意

解題思路

AC_Code

D. Max Median

題目鏈接

題目大意

解題思路

AC_Code

E. Paired Payment

題目鏈接

題目大意

解題思路

AC_Code

VirMach 便宜 VPS

QNews

Codeforces Round #703 (Div. 2) (A~E)

A. Shifting Stacks

題目鏈接

題目大意

解題思路

AC_Code

B. Eastern Exhibition

題目鏈接

題目大意

解題思路

AC_Code

C1&C2.Guessing the Greatest

題目鏈接

題目大意

解題思路

AC_Code

D. Max Median

題目鏈接

題目大意

解題思路

AC_Code

E. Paired Payment

題目鏈接

題目大意

解題思路

AC_Code

分享此文：

Related Posts

DL基礎補全計劃(五)—數值穩定性及參數初始化（梯度消失、梯度爆炸）

windows上傳ipa到蘋果開發者中心（app store）的方法

Linux作業系統

PHP反序列化字元串逃逸

VirMach 便宜 VPS

QNews

熱門搜尋