一百五十天一千题 （DAY 1）

目前总题数： 0

目前CF分数： 1325

T1： （ABC 268）C – Chinese Restaurant

// 题解
const int N = 1e6 + 10;
/*
	模拟即可
	但是纯暴力是N^2的 会TLE
	考虑到要把 A[I] 移动到 p=I-1
	需要操作 a[i] - p % N 或者 (a[i]-p+1)%N
	或者 (a[i]-p-1)%N;
	用一个东西储存一下 x次操作的贡献
	输出最大贡献即可
	
	很神奇的一题（（
*/

inline void sensei()
{
    int n;
    cin >> n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    vector<int> cnt(n+1);
    
    for(int i=1;i<=n;i++){
        int pos = i-1;
        cnt[(((a[i]-pos)%n)+n)%n]++;
        cnt[(((a[i]-pos-1)%n)+n)%n]++;
        cnt[(((a[i]-pos+1)%n)+n)%n]++;
    }
    int ans = -inf_ll;
    for(int i=0;i<=n;i++){
        ans = max(ans,cnt[i]);
    }
    cout << ans << endl;
}

signed main()
{
    sensei();    
    return 0;
}

T2 (ABC 267)C – Index × A(Continuous ver.)

/*
    题目的意思大概就是
    给定一个长度为n的序列a
    以及一个数字m
    要你找到一个长度为m的子序列b
    并且 sigma(bi*i) 最大
*/

/*
题解：
如果暴力写这题，必定会超时
因为时间复杂度为 O(N^2)

但是我们可以通过观察发现一个式子：
例如样例：

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

我们只看前两组m

分别是 
alls = (-3)*1 + (1)*2 + (-4)*3 + (1)*4
alls =          (1)*1 + (-4)*2 + (1)*3 + (-5)*4

这么一看是不是有点做差求和内味了

于是我们得到了一个alls转移的式子：

alls = a[r]*m + (alls - pre[r-1] - pre[l-2]);
其中 r是当前枚举的子序列的右端点，l是左端点

通过这个式子我们可以写出这题
详细见代码

*/


inline void sensei()
{
    int n,m;
    cin >> n >> m;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    vector<int> pre(n+1);
    for(int i=1;i<=n;i++){
        pre[i] = pre[i-1] + a[i];
    }
    int l,r;
    r = m+1;
    l = 2;
    int alls = 0;
    int ans = -inf_ll;
    for(int i=1;i<=m;i++){
        alls += i*a[i];
    }
    ans = alls;
    while(r <= n){
        alls = a[r]*m+(alls-(pre[r-1]-pre[l-2]));
        ans = max(ans,alls);
        l++;
        r++;
    }
    cout << ans << endl;
}

signed main()
{
    sensei();
    return 0;
}

T4 （ABC 267）D – Index × A(Not Continuous ver.)

/*
	题目含义：
		给你一个长度为n的数组a
		你需要在里面找到一个长度为m的子序列b
		并且 sigma(bi*i) 最大
*/

/*
	题解：
		这题相对于上一题来说，他的数据范围变小了
		M和N都在2000以内
		因此可以考虑一个O(N^2)的做法
		所以我们会考虑能不能dp
		
		定义一个数组 f[][]表示状态
		f[i][j] 表示在前i个数里选j个数组成b的最大值
		状态转移：
			f[i][j] = max(f[i-1][j-1]+a[i]*j,f[i-1][j]);
			
		
*/


inline void sensei()
{
	int n, m;
	cin >> n >> m;
	vector<int> a(n + 1);
	vector<vector<int>> f(2005, vector<int>(2005, -inf_ll));
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i <= n; i++) {
		f[i][0] = 0;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1;j <= m; j++) {
        	if(j <= i )
                f[i][j] = max(f[i - 1][j - 1] + a[i] * j, f[i - 1][j]);
		}
	}
	cout << f[n][m];
}

signed main()
{
	sensei();
	return 0;
}

T5: (CF TON ROUND(DIV1+DIV2)) B. Luke is a Foodie

/*
	题解： 当找到一个区间的最大值和最小值之差大于2*x，cnt++
*/
inline void sensei()
{
    int n,x;
    cin >> n >> x;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    
    int cnt = 0;
    int alls = 2*x;
    int minn = a[1];
    int maxn = a[1];
    
    for(int i=2;i<=n;i++){
        if(a[i] > maxn){
            maxn = a[i];
        }
        if(a[i] < minn){
            minn = a[i];
        }
        if(maxn - minn > alls) {
            cnt ++;
            minn = a[i];
            maxn = a[i];
        }
    }
    cout << cnt << endl;
}

signed main()
{
    int t;
    cin >> t;
    while(t --){
        sensei();
    }
    return 0;
}

T6 (CF ROUND 795 DIV.2)C. Sum of Substrings

/*
	题目描述：
		题目的大概意思就是
		给你一个只包含0和1的字符串s
		定义f(s) 为这个字符串每两个连续字符代表的十进制的和
		现在你有k次操作去换任意两个相邻字符
		输出f(s)可能的最小值
*/


/*
	题解： 
		贪心即可
		通过观察我们发现
		字符串里面除了第一个字符和最后一个字符出现了'1'  其他地方出现了1 必定对f(s)贡献了11
		而如果我们把某个不是在最后的字符移到了最后，那么 f(s) -= 10
		如果我们把某个不是第一的字符移动到了第一那么f(s) -= 1
		因此我们需要贪心，先考虑能不能移到最后，再考虑能不能移到第一
		注意如果字符串本身全为0那么直接输出0即可

*/



inline void sensei()
{
    int n,k;
    cin >> n >> k;
    int cnt = 0;
    string s = "";
    cin >> s;
    s = " " + s;
    for(int i=1;i<=n;i++){
        if(s[i] == '1'){
            cnt++;
        }
    }
    if(cnt == 0){
        cout << 0 << endl;
        return ;
    }
    int ans = 11*cnt;
    int st,ed;
    st = ed = 0;
    for(int i=1;i<=n;i++){
        if(s[i] == '1'){
            st = i;
            break;
        }
    }

//   debug(s.size());
    for(int i=n;i>=1;i--){
        if(s[i] == '1'){
            ed = i;
            break;
        }
    }
    
    if(st!=ed and st-1+n-ed<=k){
        ans -= 11;
    }else if(k>=n-ed){
        ans -= 10;
    }else if(k>=st-1){
        ans -= 1;
    }
    cout << ans << endl;
    
}

signed main()
{
    fuckios
    int t;
    cin >> t;
    while(t --){
        sensei();
    }
    return 0;
}

快1点了。。。写不动了。。。休息一下。。明天继续