目錄

I（簽到）

題目簡述：

思路：

代碼：

A（二分答案）

題目簡述：

思路：

代碼：

K（構造）

題目：

思路：

代碼：

?F（后綴和+排序）

題目：

思路：

代碼：

---

https://codeforces.com/gym/105385

I（簽到）

題目簡述：

判斷一個字符串首位字符是否相同，如果初試狀態不相同，是否可以經過整體左移后使其相同，如果相同輸出左移次數，否則輸出-1；

思路：

整體左移的操作是牽一發而動全身的，所以只有有倆相同且相鄰字符時才可以通過左移操作使其符合條件

代碼：

#include<bits/stdc++.h>
using namespace std;
#define int long long
//typedef long long ll;
#define endl "\n"
#define PII pair<int,int>
//#define x first
//#define y second
//priority_queue<int, vector<int>, greater<int>> pq;//小根堆
//{并查集
//int fa[N];
//int n;
//void init(){
//	for(int i=0;i<=n;i++)fa[i]=i;
//}初始化
//int get(int x){
//	return fa[x]=(fa[x]==x?x:get(fa[x]));
//}查找
//void merge(int a,int b){
//	fa[get(a)]=get(b);
//}合并
//}
const int N=2e5+10;
void solve(){string s;cin >> s;if(s[0]==s[s.size()-1]){cout << 0 << endl;return ;}
特判一開始就符合條件的情況for(int i=0;i<s.size()-1;i++){if(s[i]==s[i+1]){cout << i+1 << endl;return ;}}cout <<-1 << endl;	
}	 
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int q;cin >> q;while(q--)solve();
}

A（二分答案）

題目簡述：

使用n臺打印機同時打印k份試題，每臺打印機都是周期性工作，第i臺打印機，每ti秒打印一份，每打印li份就要休息wi秒，問打印完所需要的最短時間；

思路：

很明顯是一個二分答案，且是最大值最小類型（時間越多越能完成打印任務，xxx√√√，找第一個對號，最大值當中符合條件的最小值）

確定完二分后就要寫check函數，我們二分時間，然后找當前時間內所有打印機能打印的最大份數，如果份數>k返回1，否則返回0

那么如何確定最大份數呢？我們可以把每一周期看做每一段，根據時間可以算得有多少段，有多少段就有多少個li

因為不一定是完整周期，所以我們還要考慮，最后一段不完整的區間，用剩下的時間除以ti，但是需要注意這個結果可能會越界到wi時間里，也就是說剩下的時間除以ti的值最大只能是li

這個二分還要注意一下邊界，右邊界需要設置大一點；

代碼：

#include<bits/stdc++.h>
using namespace std;
#define int long long
//typedef long long ll;
#define endl "\n"
#define PII pair<int,int>
//#define x first
//#define y second
//priority_queue<int, vector<int>, greater<int>> pq;//小根堆
//{并查集
//int fa[N];
//int n;
//void init(){
//	for(int i=0;i<=n;i++)fa[i]=i;
//}初始化
//int get(int x){
//	return fa[x]=(fa[x]==x?x:get(fa[x]));
//}查找
//void merge(int a,int b){
//	fa[get(a)]=get(b);
//}合并
//}
const int N=2e5+10;
int t[N],l[N],w[N];int n,k;
bool check(int x)
{int num=0;int p=x;for(int i=1;i<=n;i++){p=x;
//		if(p/t[i]<=l[i]){
//			num+=p/t[i];
//			continue;
//		}int q=t[i]*l[i]+w[i];num+=p/q*l[i];p-=p/q*q;if(p/t[i]<=l[i])num+=p/t[i];else num+=l[i];if(num>=k)return 1;}return 0;
}
void solve(){cin>> n >>k;for(int i=1;i<=n;i++){cin >> t[i] >> l[i] >> w[i] ;}	int l=1,r=2e18;while(l+1!=r){int mid=l+r>>1;if(check(mid))r=mid;else l=mid;}cout << r << endl;
}	 
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int q;cin >> q;while(q--)solve();
}

K（構造）

題目：

注意是不同行相同列

思路：

上面n-2行設置成i，然后最后兩行前面n-2個數是從n-1—2*n-4

代碼：

#include<bits/stdc++.h>
using namespace std;
#define int long long
//typedef long long ll;
#define endl "\n"
#define PII pair<int,int>
//#define x first
//#define y second
//priority_queue<int, vector<int>, greater<int>> pq;//小根堆
//{并查集
//int fa[N];
//int n;
//void init(){
//	for(int i=0;i<=n;i++)fa[i]=i;
//}初始化
//int get(int x){
//	return fa[x]=(fa[x]==x?x:get(fa[x]));
//}查找
//void merge(int a,int b){
//	fa[get(a)]=get(b);
//}合并
//}
const int N=2e5+10;
void solve(){int n;cin >>n;cout << "Yes" <<endl;if(n>3){int a=2*n-3,b=2*n-2,c=2*n-1,d=2*n;
最后四個數單獨揪出來for(int i=1;i<=n-2;i++){for(int j=1;j<=n;j++){cout << i << ' ' ;}cout << endl;;}
前n-2行都為iint js=0;for(int i=1;i<=2;i++){for(int j=n-1;j<n-1+n;j++){js++;if(js==n-1)cout << a << ' ';else if(js==n)cout << b << ' ';else if(js==2*n-1)cout << c << ' ';else if(js==2*n)cout << d << ' ';else cout << j <<' ';}cout << endl;}}if(n==2){cout << 1 << ' ' <<2 << endl;cout << 3 << ' ' << 4 << endl;}if(n==3){cout << 3 << ' ' << 2 << ' ' << 6 << endl;cout << 4 << ' ' << 3 << ' ' << 3 << endl;cout << 3 << ' ' << 1 << ' ' << 5 << endl;}
}	 
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int q=1;
//	cin >> q;while(q--)solve();
}

?F（后綴和+排序）

題目：

思路：

1. 前綴和逆序處理：從后往前計算數組?a?的前綴和，將原數組轉化為后綴和數組形式，a[i]?變為從?i?到?n?的元素和 。
2. 排序：對?a[2]?到?a[n]?排序，此時數組從大到小排列（a[1]?是原數組所有元素和，單獨處理 ）。
3. 輸出結果：
   • 先輸出?a[1]，這是?k = 1?時的結果 。
   • 然后依次累加并輸出后續元素，每次累加對應增加一段，實現對不同?k?值結果的計算與輸出?

代碼：

#include<bits/stdc++.h>
using namespace std;
#define int long long
//typedef long long ll;
#define endl "\n"
#define PII pair<int,int>
//#define x first
//#define y second
//priority_queue<int, vector<int>, greater<int>> pq;//小根堆
//{并查集
//int fa[N];
//int n;
//void init(){
//	for(int i=0;i<=n;i++)fa[i]=i;
//}初始化
//int get(int x){
//	return fa[x]=(fa[x]==x?x:get(fa[x]));
//}查找
//void merge(int a,int b){
//	fa[get(a)]=get(b);
//}合并
//}
const int N=5e5+10;
int a[N];
void solve(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=n-1;i>=1;i--)a[i]+=a[i+1];sort(a+2,a+n+1);int sum=a[1];cout<<sum<<" ";for(int i=n;i>=2;i--) {sum+=a[i];cout<<sum<<" ";}cout<<endl;
}	 
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int q=1;cin >> q;while(q--)solve();
}