目录
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（后缀和+排序）
题目：
思路：
- 前缀和逆序处理：从后往前计算数组
a的前缀和，将原数组转化为后缀和数组形式，a[i]变为从i到n的元素和 。 - 排序：对
a[2]到a[n]排序，此时数组从大到小排列（a[1]是原数组所有元素和，单独处理 ）。 - 输出结果：
- 先输出
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();
}
