P152SUMI – ptit

Đề bài:


Thuật toán:


Tạo một mảng quy hoạch có dạng
xau[i]==xau[i+1]? arr[i+1]=arr[i]+1 : arr[i+1]=arr[i];
với arr[0]=0;
VD: #..###
ta có;
arr[0] = 0;
arr[1] = 0; (#.)
arr[2] = 1; #(..)
arr[3] = 1; #.(.#)
arr[4] = 2; #..(##)
arr[5] = 3; #..#(##)

arr[i+1] = số cặp kí tự giống nhau từ xâu[0 -> i];
-> Với mỗi truy vấn ta có:
Số cặp giống nhau từ l->r = arr[r-1] – arr[l-1];

Code:


#include <iostream>
#include <string>
using namespace std;
 
int main ()
{
	string xau;
	cin>>xau;
	int arr[100005];
	arr[0]=0;
	for (int i=0; i<xau.size()-1; i++)
	{
		if (xau[i]==xau[i+1])
			arr[i+1]=arr[i]+1;
		else
			arr[i+1]=arr[i];
	}
	int m;
	cin>>m;
	for (int i=1; i<=m; i++)
	{
		int l, r;
		cin>>l>>r;
		cout<<arr[r-1]-arr[l-1]<<endl;
	}
	return 0;
}

P171SUMB – ptit

Đề bài:

Thuật toán:

  • Gọi \(cnt[i]\) là số các số chia mod k = i trong tập \(S\).
  • Theo đề bài ta có: \(KQ = KQ + max(cnt[i], cnt[k-i])\) với \(i=1..k/2\).
    • Chú ý nếu n mod 2 = 0 thì ta không cộng \(cnt[n/2]\) vào KQ mà chỉ cộng 1 thôi.

Code:

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int n, k, i, j, a[200004], cnt[500], ans;
int main() {
    cin >> n >> k;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<=n; i++) {
        a[i] = a[i] % k;
        ++cnt[a[i]];
    }
    for (int i=1; i<=k/2; i++) {
        ans = ans + max(cnt[i], cnt[k-i]);
    }
    if (k%2 == 0) {
        ans -= cnt[k/2];
        if (cnt[k/2]>0) ans++;
    }
    if (cnt[0] > 0) ans++;
    cout << ans;
	return 0;
}