img

牛客周赛28

小红的新周赛

求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int res = 0;
    for (int i = 0; i < 6; i++) 
    {
        int v;
        cin >> v;
        res += v;
    }
    cout << res << endl;
    return 0;
}

小红的字符串

直接开始模拟

计入所有字符串出现次数

然后直接扔进去输出即可

天然排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
int main()
{ 
    // 26 * 26天然保序
    int cnt[26][26] = {0};
    string s;
    cin >> s;
    int n = s.length();
    for (int i = 0; i < n - 1; i++) {
        int p1 = s[i] - 'a';
        int p2 = s[i + 1] - 'a';
        cnt[p1][p2]++;
    }
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
            string ts = "";
            ts.push_back((char)(i + 'a'));
            ts.push_back((char)(j + 'a'));
            for (int t = 0; t < cnt[i][j]; t++) {
                cout << ts << endl;
            }
        }
    }
    
}

也有不天然的排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std; 
typedef long long LL;
typedef pair<int,int> PII; 
const int N=200010,M=4;
int n,m;
int a[N],s[N],st[N]; 
void solve()
{   
    string str;
    cin>>str;     
    vector<string> v;
    for(int i=0;i<str.size()-1;i++)
    {
        string s;
        s+=str[i];
        s+=str[i+1];
        v.push_back(s);
    }
    sort(v.begin(),v.end());
     
    for(auto t:v)
    {
        cout<<t<<endl;
    }
}
 
int main()
{
    int T;
    // cin>>T;
    T=1;
    while(T--)
        solve();
 
    return 0;
}

小红的炸砖块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std; 
typedef long long LL;
typedef pair<int,int> PII; 
const int N=1010,M=4; 
int n,m,k;
int a[N][N],s[N],st[N]; 
void solve()
{   
    cin>>n>>m>>k;
    while(k--)
    {
        int x,y;
        cin>>x>>y;
        if(x>st[y]) st[y]++;
    }
    //至关重要的一个逻辑
    //必须是x要比已经掉下来的大，才需要加加。
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(st[j]>0)
            {
                cout<<'.';
                st[j]--;
            }
            else cout<<'*';
        }
        cout<<endl;
    }
}
 
int main()
{
    int T;
    // cin>>T;
    T=1;
    while(T--)
        solve();
 
    return 0;
}

小红统计区间

感觉就是直接滑动窗口即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main()
{  
    int n;
    int64 k;
    cin >> n >> k; 
    vector<int64> pre(n + 1, 0);
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        pre[i + 1] = pre[i] + arr[i];
    }
    //前缀和
    
    int64 res = 0LL;
    int j = 0;
    for (int i = 0; i < n; i++) 
    {
        //找到每个数和大于K的时候的下标
        //加上即可
        while (j <= i && pre[i + 1] - pre[j] >= k) {
            j++;
        }
        res += j;
    }
    cout << res << endl;    
    return 0;
}

小红的好数组

数据范围告诉我们这不是一道模拟题

已经是一道数学题了

凑和是不可能凑出来的

我们考虑凑奇数和偶数

以六个数字来看

就是

偶数，偶数，偶数，偶数，偶数，偶数

奇数，奇数，偶数，奇数，奇数，偶数

奇数，偶数，奇数，奇数，偶数，奇数

偶数，奇数，奇数，偶数，奇数，奇数

然后算出奇数个数和偶数个数

运用快速幂辅助运算

因为要有幂次级别的运算

比如从5个偶数中有放回选出五个偶数数字，显然是5的5次方，普通的Pow应该无法支持这样的运算，因此需要快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
using pii=pair<int,int>;
const int mod=1e9+7;
int n,k;
int qpow(int x,int m){
    int res=1;
    while(m){
        if(m&1) res = res*x%mod;
        x=x*x%mod;
        m>>=1;
    }
    return res;
}
int ji,ou;
void solve(){
    cin>>n>>k;
    ou = k/2;
    ji = k - ou;
    int ans = qpow(ou,n);
    int p1=(n+2)/3,p2=(n+1)/3,p3=n/3; 
    ans += qpow(ou,p1)*qpow(ji,n-p1)%mod;
    ans += qpow(ou,p2)*qpow(ji,n-p2)%mod;  
    ans += qpow(ou,p3)*qpow(ji,n-p3)%mod;  
    cout<<ans%mod<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int t=1;
    while(t--) 
    {
        solve();
    }
    return 0;
}

小红统计区间（加强版）

出现负数，滑动窗口\(×\)

并且前缀和的单调性性质不存在了

因此采取树状数组+离散化的形式进行书写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5,M = 5*N;
int n,k,idx;
int a[N],tr[M];
set<int>tmp;
unordered_map<int,int>to;
int tr[M];
void modify(int p,int x) 
{
	while(p<M) 
    {
		tr[p] += x;
		p += p&(-p);
	}
}
int query(int p) 
{
	int res = 0;
	while(p>0) 
    {
		res += tr[p];
		p -= p&(-p);
	}
	return res;
}
signed main() {
	cin>>n>>k;
	tmp.insert(0);
	for(int i=1; i<=n; i++) 
    {
		cin>>a[i];
		a[i] += a[i-1];
		tmp.insert(a[i]);
		tmp.insert(a[i]-k);
	}
	for(int i:tmp) 
    {
		to[i] = ++idx;
	}
	int ans = 0;
	modify(to[0],1);
	for(int i=1; i<=n; i++) 
    {
		int id = to[a[i]-k];
		ans += query(id);
		modify(to[a[i]],1);
	}
	cout<<ans;
}