應該可以發現字串根本不會用到吧?

Subtask 1 : \(N \le 20\)

可能拿來練習一下位元枚舉之類

Subtask2 : 無其他限制

可以將輸入進來的所有時間都轉成從 \(0\) 年開始總共經過了多久，答案就是 \(\le M \times 12+K\) 的數字數量，複雜度 \(O(N)\)
當然，排序之後二分搜或者是對值域開線段樹之類的都可以，複雜度 \(O(N\log N)\)

官解

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
 
 
 
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	int tar;
	int arr[n];
	for(auto &i:arr){
		string s;
		int a,b;
		cin>>s>>a>>b;
		i = a*100+b;
	}
	int a,b;
	cin>>a>>b;
	tar = a*100+b;
	int ans = 0;
	for(auto &i:arr)ans += (tar>=i);
	cout<<ans;
}
 

Subtask 1

位元枚舉

Subtask 2

從左到右掃，假設現在的左界是 l，枚舉起鍋時間跟他可以延伸到的右界 r 就可以了
複雜度 O(nA)

Subtask 3

承上，對於左界 l 可以維護目前的起鍋時間區間然後想辦法擴展右界
複雜度 O(n)

Subtask 1 : \(n\leq 10^3\)

枚舉每個 \(k\)，每次 \(O(n)\) 算 \(S\)

複雜度 \(O(n^2)\)

Subtask 2 : \(a_i\leq a_{i+1}\)

\(a\) 是一個遞增數列

對於一個固定的 \(k\)，最小值 \(S\) 只會發生在 \(a_0\) 或 \(b_0\) 的地方

每次只要檢查這兩個地方

複雜度 \(O(n)\)

Subtask 3 : 無其他限制

如果不知道怎麼求最大的 \(S\) 怎麼辦？

可以對 \(S\) 二分搜！

發現對於一個 \(a_i\)，會讓總和 \(\geq S\) 的 \(k\) 會是一段或兩段連續的區間

形如 \([l,r]\) 或 \([0,r],[l,n-1]\)

\(S\) 為合法的解若且為若存在至少一個 \(k\) 同時被 \(n\) 個區間包含

找被幾個區間包含的方法：

對 \([l,r]\) 或 \([0,r],[l,n-1]\) 加 \(1\)

可以利用差分

對區間 \([l,r]\) 加 \(1\) 相當於
對差分陣列的 \(d_l\) 加 \(1\)，\(d_{r+1}\) 減 \(1\)

複雜度 \(O(n\log n\log C)\) 的做法：

對每個 \(a_i\) 二分搜（lower_bound）出
\(b\) 對應到的區間

最後檢查是否有位置被加到 \(n\) 次

複雜度 \(O(n(\log n+\log C))\) 的做法：

發現當 \(a\) 的值遞增，
\(b\) 對應到區間的左界會越來越左邊

可以先將 \(a\) 排序好，
利用雙指針找對應到 \(b\) 的區間

\(O(n(\log n +\log C))\) solution

Subtask 1 : \(N \le 15\)

枚舉要用多少隻手指，再枚舉每個時間點各個手指的位置。

Subtask 2 : \(M \le 4\)

cout<<1;

Subtask 3 : \(M \le 6\)

稍微觀察一下發現只要用兩隻手指，所以如果試出來一隻手指不行就表示答案是2
可以令 \(DP_{i,j}\) 表示目前到第 \(i\) 列的譜面，手指在 \(j\) 的位置是否有解。
則\(dp_{i,j} =\) \((dp_{i-1,j-1}|dp_{i-1,j}|dp_{i-1,j+1})\) &(按在j是否可以成功打擊該列)
感性理解為何最多用兩隻: \(m = 6\) 時，將兩根手指放在 (2,4)

但是被假解唬爛過了…

...
int main(){
    cin.tie(0),ios::sync_with_stdio(0);
    cin >> t;
    while(t--){
        int maxamnt=0,cnt=0;
        cin >> n >> m;
        while(n--){
            cnt=0;
            cin >> ins;
            for(int i=2;i<m;i++){
                if(ins[i-2]=='*'&&ins[i-1]=='-'&&ins[i]=='-') cnt++;
            }
            if(ins[0]=='-'&&ins[1]=='-') cnt++;
            maxamnt=max(maxamnt,cnt);
        }
        cout << maxamnt << '\n';
    }
    uwu
}
 

Subtask 4 : 無其他限制

可以證明最多需要三隻手指
感性證明: \(m=8\) 時一隻手指在中間其中一排，剩下兩根一根顧左邊另一根顧右邊，左右兩邊都可以當成 \(m \le 4\) 的譜面

所以要寫三維版的DP跟二維版的DP跟一維的DP?

檢查用一根手指與兩根手指是否可以成功就好。
如果一隻手指有解:cout<<1
如果兩隻手指有解:cout<<2
否則cout<<3

定義 \(dp_{i,l,r}\)表示打到第 \(i\) 列的時候雙手分別在 \(l,r\) (若 \(r = -1\)表示要一隻手指打)
則 \(dp_{i,l,r} = orsum_{-1\leq d1,d2 \leq 1}(dp_{i-1,l+d1,r+d2})\) & 按在 \(l,r\) 是否可以成功打擊該列。
這樣做可以同時算一隻手指與兩隻手指的答案。

官解

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
 
const int mxn = 9;
bool dp[2][mxn][mxn];
vector<pii> keys;
vector<pii> dx;
int n,m;
 
inline bool check(pii &p){
	if(p.fs == 0&&p.sc == 0)return false;
	if(p.fs<0||p.sc<0||p.fs>m||p.sc>m)return false;
	return true;
}
 
inline bool cover(int l,int r){
	int tmp = 0;
	for(int i = 0;i<keys.size();i++){
		if(keys[i].fs<=l&&keys[i].sc>=l)tmp++;
		else if(keys[i].fs<=r&&keys[i].sc>=r)tmp++;
	}
	return tmp == keys.size();
}
 
void solve(){
	cin>>n>>m;
	bool roll = 0;
	for(int i = 0;i<=m;i++)for(int j = 0;j<=m;j++)dp[roll][i][j] = 1;
	for(int i = 0;i<n;i++){
		string s;
		cin>>s;
		s = "#"+s;
		roll ^= 1;
		keys.clear();
		for(int j = 1;j<=m;j++){
			if(s[j] == '-'){
				if(keys.empty()||keys.back().sc+1 != j)keys.push_back({j,j});
				else keys.back().sc = j;
			}
		}
		memset(dp[roll],0,sizeof(dp[roll]));
		for(int j = 0;j<=m;j++){
			for(int k = 0;k<=m;k++){
				bool flag = false;
				for(auto &d:dx){
					pii tmp = {j+d.fs,k+d.sc};
					if(j == 0&&tmp.fs != j)continue;
					if(k == 0&&tmp.sc != j)continue;
					if(check(tmp)&&dp[roll^1][tmp.fs][tmp.sc])flag = true;
				}
				if(flag&&cover(j,k))dp[roll][j][k] = true;
			}
		}
		/*
		for(auto &j:keys)cout<<j.fs<<' '<<j.sc<<',';cout<<endl;
		for(int j = 0;j<=m;j++){
			for(int k = 0;k<=m;k++){
				cout<<dp[roll][j][k];
			}
			cout<<endl;
		}
		cout<<endl;
 
	   */
	}
	for(int i = 1;i<=m;i++){
		if(dp[roll][0][i]){
			cout<<"1\n";
			return;
		}
	}
	for(int i = 1;i<=m;i++){
		for(int j = 1;j<=m;j++){
			if(dp[roll][i][j]){
				cout<<"2\n";
				return;
			}
		}
	}
	cout<<"3\n";
	return;
}
 
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(int i = -1;i<=1;i++)for(int j = -1;j<=1;j++)dx.push_back({i,j});
	int t;cin>>t;
	while(t--)solve();
}
 

Subtask 1 : \(a_i,S\) 皆為質數

如果 \(a_i = S\)那答案就是0
因為小七不可能可以變身

Subtask 2 : \(a_i,S\) 的因數數量 \(\le\) 4

以防萬一有人只想到怎麼質因數分解卻想不到建圖

Subtask 3 : \(a_i,S \leq 10 ^ 6\)

建圖，將每個數字因數分解之後，建一張二分圖，左側為 \(1,2,3,...n+1\)，右側為因數。
建 \(a_i(i \neq n+1)\) 的因數往 \(i\) 邊權 \(b_i\) 的邊，而反向建邊權為 \(0\) 的邊。
也建 \(S\) 向其因數邊權為 \(0\) 的邊 。之後由 \(S\) 開始跑最短路即可。
另一個建法是將每個數字的因數兩兩建邊，再對 \(S\) 的所有因數距離設成0跑多點源最短路。

但是這樣還是不夠快

觀察到不用對所有因數都建邊，只要建質因數就好。複雜度 \(O(NlogClogN)\)

Subtask 4 : 無其他限制

瓶頸應該在是質因數分解上，所以來優化一下。

觀察到枚舉質因數時，for 迴圈會跑過很多合數，是不必要的。
然後一個數字比 \(\sqrt C\) 大的質因數只有一個，所以枚舉質數就好
複雜度 \(O(NlogClogN + \frac {\sqrt C \times N}{ln(N)})\)

然後Subtask 3 測資太弱了…
貌似沒有卡到大質數測資

然後有人用 pollard rho 過 :EEEEE:

官解

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
 
const int mxn = 5e4+10;
const int MXN = sqrt(1e9)+1;
const ll inf = 1e18;
 
int arr[mxn];
bitset<MXN> isp;
vector<int> primes;
vector<int> all;
vector<int> facs[mxn];
vector<pll> paths[mxn*12];
ll dist[mxn*12],cost[mxn];
int n;
 
void DIJKSTRA(int start){
	fill(dist,dist+mxn*12,inf);
	dist[start] = 0;
	priority_queue<pll,vector<pll>,greater<pll>> pq;
	pq.push({dist[start],start});
	while(!pq.empty()){
		auto now = pq.top();
		pq.pop();
		if(now.fs != dist[now.sc])continue;
		for(auto nxt:paths[now.sc]){
			if(dist[nxt.fs]>dist[now.sc]+nxt.sc){
				dist[nxt.fs] = dist[now.sc]+nxt.sc;
				pq.push({dist[nxt.fs],nxt.fs});
			}
		}
	}
	return;
}
 
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(int i = 2;i<MXN;i++){
		if(!isp[i]){
			primes.push_back(i);
			for(int j = i+i;j<MXN;j+=i)isp[j] = true;
		}
	}
	cin>>n;
	for(int i = 1;i<=n;i++)cin>>arr[i];
	for(int i = 1;i<=n;i++)cin>>cost[i];
	cin>>arr[n+1];
	for(int i = 1;i<=n+1;i++){
		for(auto &j:primes){
			if(j>arr[i])break;
			if(arr[i]%j == 0){
				facs[i].push_back(j);
				while(arr[i]%j == 0){
					arr[i]/=j;
				}
			}
		}
		if(arr[i]>primes.back())facs[i].push_back(arr[i]);
		for(auto &j:facs[i])all.push_back(j);
	}
	all.push_back(0);
	sort(all.begin(),all.end());
	all.erase(unique(all.begin(),all.end()),all.end());
	for(int i = 1;i<=n+1;i++){
		for(auto &j:facs[i]){
			auto rp = lower_bound(all.begin(),all.end(),j)-all.begin();
			int lp = all.size()+i;
			if(i != n+1)paths[rp].push_back({lp,cost[i]});
			paths[lp].push_back({rp,0});
		}
	}
	DIJKSTRA(all.size()+n+1);
	assert(all.size()+n+1<mxn*12);
	for(int i = 1;i<=n;i++){
		ll ans = inf;
		for(auto &j:facs[i]){
			int p = lower_bound(all.begin(),all.end(),j)-all.begin();
			ans = min(ans,dist[p]);
		}
		if(ans==inf)cout<<"-1 ";
		else cout<<ans<<' ';
	}
	return 0;
}
 
 

上傳程式碼，不是exe

pA : 沒用到的資訊可以不用存

不然就是開全域變數
@很多人

#include<iostream>
using namespace std;
int main(){
    int n,m,k,ans=0;
    string book[10000];
    int year[10000];
    int mon[10000];
    cin>>n;
 
    for(int i=0;i<n;i++){
        cin>>book[i]>>year[i]>>mon[i];
    }
    cin>>m>>k;
}

ckpre_044
???

фдф

…
ckpre083

...
#define PCCORZ true
 
// $$$$    $$$$   $$$$   $$$   $$$$   $$$$$
// $   $  $      $      $   $  $   $     $ 
// $$$$   $      $      $   $  $$$$     $  
// $      $      $      $   $  $ $     $   
// $       $$$$   $$$$   $$$   $  $   $$$$$
 
const int MXN = 100005;
...

ckpre076
先cin>>n…

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    long long n;
    vector <long long> a(n), b(n);
 
    cin >> n;
    for (int i=0;i<n;i++){
        cin >> a[i];
    }
    for (int i=0;i<n;i++){
        cin >> b[i];
    }
 
    long long S = -1, s = 100000000000000000;
    long long sum = 0;
 
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            sum = a[(i+j)%n]+b[j];
            s = min(s,sum);
        }
        S = max(S,s);
        s = 100000000000000000;
    }
 
    cout << S << endl;
}
 

把judge當成編譯器