10月训练(部分

//http://codeforces.com/problemset/problem/1690/E
//利用set数组 里面储存的是 每一个数字%k之后的数字,由于特殊性,一个数大于k,那么就算这个数+0他对答案的贡献最少也是 m/k的价值
//所以可以直接计算价值,然后第二位储存编号,便于分辨
//遍历set数组,取第一s,由于set数组内自动排序,所以利用内置二分找出第一个大于等于 k-i的数,由于两者加起来是最接近k的,所以损失一定最小,答案一定最大

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
int n,t,a[N],f[N],res,num,ans,m,k;
bool vis[N];
void solve()
{
    cin>>n>>k; res=0;
    set<pair<int,int>>s;
    for(int i=1;i<=n;i++){
        cin>>m;
        res+=m/k,s.insert({m%k,i});
    }
    while(!s.empty()){
        auto it=s.begin();
        auto x=*it;
        s.erase(it);
        auto it2=s.lower_bound({k-x.first,-1});
        if(it2==s.end()) it2=s.begin();
        auto y=*it2;
        s.erase(it2);
        if(x.first+y.first>=k) res++;
    }
    cout<<res<<endl;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

//http://codeforces.com/problemset/problem/1492/C

//正向扫一遍,求出这个字符串中第一个出现模板串中字符的位置,并记录在h数组
//反向扫一遍,记录在e数组
//对于模板里面的每一个字符,由于我们需要让代价最大,即两相邻字符的间距最大
//那么对于每一个字符,他与上一次字符的最大距离一定是,上一个字符第一次出现的位置和这个字符最后出现位置的差值,取最大值即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s,ss;
int n,t,h[N],e[N],res,num,ans,m,k;
bool vis[N];
void solve()
{
    cin>>n>>m>>s>>ss;
    for(int i=0,j=0;i<n;i++)
        if(s[i]==ss[j]) h[j++]=i;
    for(int i=n-1,j=m-1;i>=0;i--)
        if(s[i]==ss[j]) e[j--]=i;
    for(int i=1;i<m;i++) res=max(res,e[i]-h[i-1]);
    cout<<res;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    solve();
    return 0;
}

//https://codeforces.com/problemset/problem/1680/C

//由于我们要去前去后,所以我们最后得到的一个区间为[l,r],贪心的去想
//对于一个固定的l,我们的r越大,则1就越少,0就越多,即区间内代价越大,区间外代价越小
//那么令r为n,则有,r越小,0越少,1越多,即代价递增,所以代价满足单调性,对代价二分即可

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,g[N],f[N],res,num,ans,m,k;
bool vis[N];
bool check(int u)
{
    for(int l=1,r=0;l<=n;l++){
        while(r<n&&f[r]-f[l-1]<=u) r++;
        if(g[n]-g[r]+g[l-1]<=u) return true; 
    }
    return false;
}
void solve()
{
    cin>>s;
    int l=0,r=s.size();
    n=s.size();
    for(int i=1;i<=s.size();i++) f[i]=f[i-1]+(s[i-1]=='0'),g[i]=g[i-1]+(s[i-1]=='1');
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

//基于上份代码的思路,由于我们固定l之后,r从小到大增加,会得到区间内代价变大,区间外代价变小
//所以当我们的区间内代价最接近区间外代价的时候,此时一定是答案,所以就有如下结论:
//1_delete=0_live,1_live+0_live=1_live+1_delete=1_size;
//所以我们只需要维护一个长度为 字符串中1的长度的窗口,然后等价滑窗即可

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m,k;
bool vis[N];
void solve()
{
    cin>>s; res=0,num=0;
    for(int i=0;i<s.length();i++) if(s[i]=='1') num++;
    int num0=0,num1=num;
    for(int i=0;i<num;i++){
        if(s[i]=='0') num0++;
        else num1--;
    }
    res=max(num1,num0);
    for(int i=num;i<s.length();i++){
        if(s[i]=='0') num0++;
        else num1--;
        if(s[i-num]=='0') num0--;
        else num1++;
        res=min(res,max(num1,num0));
    }
    cout<<res<<endl;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

//https://www.luogu.com.cn/problem/P8700
// 观察规律,只需要看最内层的,从里到外的周期分别为 4 8 12,所以内层为最小周期
//所以对于内层每一个块,它的对应块是确定的,枚举并分析即可
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
string st,ed,mid;
void solve()
{
    map<char,int>mp;
    cin>>st>>mid>>ed;
    for(int i=0;i<4;i++){
        mp[st[i]]++,mp[st[4+i]]++,mp[st[8+i]]++,mp[mid[i]]++,mp[mid[4+i]]++,mp[ed[i]]++;
        if(mp['Y']!=1||mp['R']!=2||mp['G']!=3) return cout<<"NO"<<endl,void();
        mp.clear();
    }
    cout<<"YES"<<endl;
}
int main()
{
    int t; cin>>t;
    while(t--) solve();
}