Codeforces Round 909 (Div. 3)
A. Game with Integers
显然就是还要不是三的倍数就能赢！
int n;
cin>>n;
int k;
while(n--)
{
cin>>k;
if(k%3==0){
cout<<"Second"<<endl;
}else{
cout<<"First"<<endl;
}
}
B.250 Thousand Tons of TNT
最开始直接写暴力但时间太长，没想到前缀和 区间和相关算法，所以改后：
long long t;
cin >> t;
while (t--) {
long long n;
cin >> n;
long long arr[n];
for (long long i = 0; i < n; i++) {
cin >> arr[i];
}
long long maxout = -99999999;
for (long long i = 1; i <= n; i++) {
if (n % i == 0) {
long long maxsum = -1e16;
long long minsum = 1e16;
long long sum[n + 1] = {0};
for (long long j = 0; j < n; j++) {
sum[j+1] = sum[j] + arr[j];
}
for (long long j = 0; j < n; j += i) {
long long out = sum[j+i] - sum[j];
maxsum = max(maxsum, out);
minsum = min(minsum, out);
}
maxout = max(maxout, maxsum - minsum);
}
}
cout << maxout << endl;
}
*核心思路：*
*sum为前缀和，i为选定的因子，利用j+=i来选定区间，然后通过前缀和区间和来求得区间和out即重量和，依次选取最大和最小，在所有区间选完之后再用maxout记录更新最大差。*
补题时我曾将maxsum和minsum定义为99999999....然后样例一中的：
4
1000000000 1000000000 1000000000 1000000000
此组数据一直过不了，最后才发现9开少了，刚好少一个1。。。。。。。。
C. *Yarik and Array*
*本来思路是一直加直到abs(arr[i]%2)==abs(arr[i+1]%2)，但是过一遍样例发现3过不了才发现要是arr[ ]前几个元素较小（负数）且交替奇偶呢？那么就要用sum减小的元素之和（所以也相当于两个子序列的题）。*
int t,n;
cin>>t;
while(t--)
{
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int out=arr[0];
int sum=arr[0],minsum=min(0,arr[0]);
for(int i=1;i<n;i++)
{
if(abs(arr[i]%2)==abs(arr[i-1]%2))//更新子数组
{
minsum=0;
sum=0;
}
sum+=arr[i];
out=max(out,sum-minsum);
minsum=min(minsum,sum);
}
cout<<out<<endl;
}
用sum来累加子序列总和，minsum来累加子序列中的最小和，if(abs(arr[i]%2)==abs(arr[i-1]%2)){minsum=0;sum=0;}更新子序列并更新sum和最小和。最终结果就是更新后的sum-minsum，minsum=min(minsum,sum);这个以sum为一个值来进行比较更新。
D. Yarik and Musical Notes
两个数组ai，bi,bibj=bjbi。取以二为底对数可以发现其实就是ai/bi=aj/bj，最开始开指数发现数据太大，longlong也不够，所以想了再取一次对数即brr[i]=(double)log(arr[i])/log(2);
abs(brr[i]-arr[i]-brr[j]+arr[j])<1e-1这样来过，测试发现最后一个测试点过不了。。。。。数据太多了tle，所以回到最初取对数的时候，将其取ln即lni/i=lnj/j，整数来说：也就2,4会相等。。。。。。。。。。。。。。。。。。。。
所以原式相当于（1,2）可以成立，只需遍历得到其出现次数和一个相同的数出现的次数：
long long t;
scanf("%lld",&t);
long long n,count,num;
while(t--)
{
cin>>n;
long long arr[n];
count=0,num=0;
for(long long i=0;i<n;i++)
{
scanf("%lld",&arr[i]);
if(arr[i]==1||arr[i]==2)
{
num++;
}
}
sort(arr,arr+n);
long long h=0;
for(long long i=0;i<n-1;i++)
{
if(arr[i]==arr[i+1]&&arr[i]!=1&&arr[i]!=2)
{
h++;
}
if(arr[i]!=arr[i+1]||i+2==n)
{
count+=h*(h+1)/2;
h=0;
}
}
printf("%lld\n",count+num*(num-1)/2);
}
做题的时候我用的cin来读入，但是tle了换成scanf一下就过了。。。所以以后就用scanf了
E. Queue Sort
这个题做了好久都是模拟题目给的步骤，实在没法就自己带了几组数据然后发现似乎就是找规律。
先用min找到最小值及下标，然后查看其后面数组元素是否有序（其实能排好的话就是有序，然后输出最小值的下标）要是后面序列无序，那么不会交换后面的值，就是说无法排序。
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int min= 0;
for (int i = 0; i < n; i++) {
if (a[i] < a[min]) {
min = i;
}
}
for (int i = min + 1; i < n; i++) {
if (a[i] < a[i - 1]) {
cout << -1 << endl;
return;
}
}
cout << min << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}