书脊 | 这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Codeforces Round #719 (Div. 3)D. Same Differences

给一个数组, 求有多少对数, 里面的数字差等于index差.

数字差= index差, 可以转化成, 数字与index的差等于另一个数字与index的差. 所以用set找即可.

注意问的是多少对pair, 最后要乘起来后/2

#include "bits/stdc++.h"
using namespace std;   
// fast read
const auto fr = [](){
    std::ios_base::sync_with_stdio(0); std::cin.tie(0);
    std::cout << std::fixed << std::setprecision(12);
    return 1;
}();
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
	cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.first;
	return cin >> p.second;
}
// vars:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
// consts
ll M = 0;
// ksm (kuai su mi)
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}

int main() { 
    fr; 
    int T;
	cin >> T;
	while (T--)
	{ 
		int N;
		cin >> N;
		unordered_map<ll, ll> A;
		for (int i = 1; i <= N; i++)
		{ 
			int n;
			cin >> n;
			A[n - i]++;
		}
		ll res = 0;
		for(auto a : A)
		{
			if(a.second > 1)
				res += a.second * (a.second - 1);
		}
		cout << res / 2  << endl;
	}
	
    return 0; 
}

Date July 1, 2021
Category Codeforces
Comments No Comments

Codeforces Round #719 (Div. 3)C. Not Adjacent Matrix

给数字n, 求一个n x n的矩阵, 每两个相邻个子的大小之差不能是1.

先放单数1 3 5 7, 再放2 4 6 8 即可.

#include "bits/stdc++.h"
using namespace std;   
// fast read
const auto fr = [](){
    std::ios_base::sync_with_stdio(0); std::cin.tie(0);
    std::cout << std::fixed << std::setprecision(12);
    return 1;
}();
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
	cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.first;
	return cin >> p.second;
}
// vars:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
// consts
ll M = 0;
// ksm (kuai su mi)
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}

int main() { 
    fr; 
    int T;
	cin >> T;
	while (T--)
	{ 
		int N;
		cin >> N;
		if(N == 1)
		{
			cout << 1 << endl;
			continue;
		}
		if(N == 2)
		{
			cout << -1 << endl;
			continue;
		} 
		int count = 1;
		for (int i = 1; i <= N * N ; i+=2)
		{
			
			cout << i << " ";
			if((count ) % N == 0)
			{
				cout << "\n";
			}
			count++;
		}
		for (int i = 2; i <= N * N ; i+=2)
		{
			
			cout << i << " ";
			if((count ) % N == 0)
			{
				cout << "\n";
			}
			count++;
		}
		
	}
	
	
    return 0; 
}

Date July 1, 2021
Category Codeforces
Comments No Comments

Codeforces Round #719 (Div. 3)B. Ordinary Numbers

给一个整数n, 问[1,n]的区间中有多少个digit全部相同的数字.

这题就看一下啥时候想通, 1到9有9个, 然后11到99有9个, 111到999有9个…所以看出来是和1的个数与最高项的比有关.

#include "bits/stdc++.h"
using namespace std;   
// fast read
const auto fr = [](){
    std::ios_base::sync_with_stdio(0); std::cin.tie(0);
    std::cout << std::fixed << std::setprecision(12);
    return 1;
}();
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
	cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.first;
	return cin >> p.second;
}
// vars:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
// consts
ll M = 0;
// ksm (kuai su mi)
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}

int main() { 
    fr; 
    int T;
	cin >> T;
	while (T--)
	{ 
		int N;
		cin >> N;
		ll base = 1; // 1, 11, 111, 1111, 11111
		ll res = 0;
		for (int i = 1; i <= 9; i++)
		{
			for (int j = 1; j <= 9; j++)			
			{
				if(base * j <= N)
				{
					res ++;
				}
			}
			base = base * 10 + 1;
		}
		cout << res << endl;
	}
	
    return 0; 
}

Date July 1, 2021
Category Codeforces
Comments No Comments

Codeforces Round #719 (Div. 3)A. Do Not Be Distracted!

给一个string, 问是不是有重复出现过的不连续的char.

用set直接解决即可.

#include "bits/stdc++.h"
using namespace std;   
// fast read
const auto fr = [](){
    std::ios_base::sync_with_stdio(0); std::cin.tie(0);
    std::cout << std::fixed << std::setprecision(12);
    return 1;
}();
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
	cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.first;
	return cin >> p.second;
}
// vars
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
// consts
ll M = 0;
// ksm (kuai su mi)
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}

int main() { 
    fr; 
    int T;
	cin >> T;
	while (T --)
	{
		int N;
		cin >> N;
		int check[26] = {};
		string s;
		cin >> s;
		int flag = 0;
		for (int i = 0; i < N; i++)
		{ 
			if(check[s[i] - 'A'] && i > 0 && s[i - 1] != s[i])
			{
				flag++;
				break;
			}
			check[s[i] - 'A']++;
		}
		if(flag)
		{
			cout << "NO" << endl;
		}
		else 
		{
			cout << "YES" << endl;
		}

	}
	
    return 0; 
}

Date July 1, 2021
Category Codeforces
Comments No Comments

Codeforces Round #728 (Div. 2)C. Great Graphs

这题说给一个数组, 任意两个数字都可以建一个路, 求路的负数最大是多少.

这题就画一画, 比如 0 2 5 7 10, 那么可以建立任何两个数字之间的路, 和是0. 那么5->0, 7->(0,2,), 10->(0,2,5), 都是答案要的负数路. 很简单的模式.

#include "bits/stdc++.h"
using namespace std;   
const auto fr = [](){
    std::ios_base::sync_with_stdio(0); std::cin.tie(0);
    std::cout << std::fixed << std::setprecision(12);
    return 1;
}();

template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
	cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.first;
	return cin >> p.second;
}

// vars:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
int main() { 
    fr; 
    int T;
    cin >> T;
    while (T --)
    {
        int N;
        cin >> N;
        ll A[N + 1]={};
        for (int i = 1; i <= N; i++)
        {
            cin >> A[i];
        } 
        sort(A+1, A+N+1);
        if(N < 3)
        {
            cout << 0 << endl;
            continue;
        } 
        ll res = 0; 
        ll pre[N + 2]={};
        for (int i = 1; i <= N; i++)
        {
            pre[i + 1] = pre[i] + A[i];
        } 
        for (int i = 3; i <= N; i++)
        {
            res -= ((i - 2) * A[i] - pre[i - 1] );
        }
        
        cout << res << endl;
    }
    
    return 0; 
}

Date June 27, 2021
Category Codeforces
Comments No Comments

Codeforces Round #728 (Div. 2)B. Pleasant Pairs

给一个数组, 求两个数字相乘等于index想加的pair的个数.

因为是index想加, 所以已知index的大小是从3(1+2)到2*n. 我们就按个找每个数, 看看有多少pair. 因为A[i]*A[j]=[1,2*n], 那么就知道其中一个是的范围肯定是[1, sqrt(n)]. 所以只要是i能整除j的, 都是答案的可能性.

#include "bits/stdc++.h"
using namespace std;   
const auto fr = [](){
    std::ios_base::sync_with_stdio(0); std::cin.tie(0);
    std::cout << std::fixed << std::setprecision(12);
    return 1;
}();

template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
	cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.first;
	return cin >> p.second;
}

// vars:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
int main() { 
    fr; 
    int T;
    cin >> T;
    while (T--)
    {
        int N;
        cin >> N; 
        int res = 0;
        int A[2*N + 1];
        for (int i = 0; i < 2*N + 1; i++)
        {
            A[i] = INT_MAX  ;
        }
        
        for (int i = 1; i <= N; i++)
        { 
            int C;
            cin >> C;
            A[C] = i; 
        }
        
        for (int i = 1; i < 2 * N; i++)
        { 
            for (int j = 1; j <= sqrt(i); j++)
            {
                if(i % j == 0 && i != j*j && A[j] + A[i/j] == i)
                    res++;
            }
        }
        cout << res << endl;
    }
    
    return 0; 
}

Date June 27, 2021
Category Codeforces
Comments No Comments

Codeforces Round #728 (Div. 2)A. Pretty Permutations

给n个数字, 从1开始到n, 求距离最小的每个数都不在自己位置上的数组.

因为要距离最小, 所有前后swap一下即可. 注意如果是奇数,要多swap一下.

#include "bits/stdc++.h"
using namespace std;   
const auto fr = [](){
    std::ios_base::sync_with_stdio(0); std::cin.tie(0);
    std::cout << std::fixed << std::setprecision(12);
    return 1;
}();

template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
	cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.first;
	return cin >> p.second;
}

// vars:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
int main() { 
    fr; 
    int T;
    cin >> T;
    while (T --)
    {
        int N;
        cin >> N;
        int A[N];
        for (int i = 1; i <= N; i++)
        {
            A[i - 1] = i;
        }
        for (int i = 1; i < N; i+=2)
        {
            swap(A[i],A[i - 1]);
        }   
        if(N % 2 != 0)
        {
            swap(A[N - 1], A[N - 2]);
        }
        for (int i = 0; i < N; i++)
        {
            cout << A[i] << " ";
        }
        cout << endl;
        
    }
   
    return 0; 
}

Date June 27, 2021
Category Codeforces
Comments No Comments

Largest Odd Number in String

给一个string, 求最大的是奇数的substring.

这题就是从后往前找, 如果看到一个奇数就停止就行了.

class Solution {
public:
    string largestOddNumber(string num) {
        for(int i = num.length() - 1; i >= 0; i--)
        {
            if((num[i] - '0') % 2 != 0)
                return num.substr(0, i + 1);
        }
        return "";
    }
};

Date June 25, 2021
Category Leetcode
Comments No Comments

Codeforces Round #727 (Div. 2)D. PriceFixed

给N个pairs, 里面第一个数字是需要买几个, 第二个数字是买多少个后可以有优惠价格. 问花多少钱能买够所有需要买的物品.

因为每个物品价格都是一样的,相当于二元店, 买够第一个数字就变成了一元店. 那么我们想花最少钱, 肯定要买最多的打折物品, 但是打折物品需要买够两元的物品才能买, 所以我们按照从小到大的顺序排序好打折物品需要买多少才能买. 然后我们设买够n个物品后, 可以开始买打折物品, 因为我们知道如果买n个可以, 那么买n+1也可以, 所以问题转化成为如何找到n的lower_bound. 这里用二分查找,

方法check就是验证是否存在n个打折物品的可能. 验证方法如下, 假设total是一共要买的物品, 我们知道total-n, 就是没有当前状态下没有打折的物品的数量. 那么我们从最少的需要物品数量就可以买打折物品的物品开始, 如果当前物品的需要购买数量已经大于total-n, 就证明当前这个不能拿了, 于是我们因为拿不到n个物品, 所以return false. 如果当前物品的需要购买数量小于等于total-n, 就证明当前这个可以拿, 我们把它加进来变成total-n+A[i].first, 然后n -= A[i].first, 这样一直找下去, 直到n==0.

#include "bits/stdc++.h"
using namespace std;   
#define fr ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back;
typedef int64_t ll;
typedef pair<ll, ll> pll;
int main() { 
    fr; 
	ll N;
	cin >> N;
	pll A[N];
	ll total = 0;
	for(int i = 1; i <= N; i++) 
	{
		cin >> A[i].second >> A[i].first;
		total += A[i].second;
	}
	sort(A + 1, A + N + 1);
	ll left = 0;
	ll right = total;
	ll res = 0;
	auto check = [&](ll n) -> bool 
	{
		ll cur = total - n; // n is the number of discounted items, cur is the items wit origal price
		for(int i = 1; i <= N; i++) 
		{
			if (A[i].first > cur)
			{
				return false;
			}
			ll taken = min(A[i].second, n); // buy all A[i] in discounted price
			cur += taken;
			n -= taken;
			if(n == 0)// we found all available n
				return true;			
		}
		return true;
	};
	while (left < right)
	{
		ll mid = left + (right - left) / 2;
		if (check(mid))
		{
			left = mid + 1;
			res = mid;
		}
		else
		{
			right = mid;
		}
		
	} 
	cout << 2 * total - res << endl;
    return 0; 
}

Date June 22, 2021
Category Codeforces
Comments No Comments

Codeforces Round #727 (Div. 2)C. Stable Groups

给一个数组, 求加入n个数字(大小不限)后, 使得数组中两个的差不大于k. 求n是多少.

这题贪心, 就是每次都取加入最大的数字.

#include "bits/stdc++.h"
using namespace std;   
#define fr ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int main() { 
    fr;
    int64_t N,K,X;
    cin >> N >> K >> X;
    int64_t A[N + 1];
    for(int i = 1; i <= N; i++)
    {
        cin >> A[i];
    }
    sort(A + 1, A+N+1);
    int64_t res = 1;  
    vector<int64_t> v;
    for(int i = 1; i < N; i++) 
    { 
        v.push_back((A[i + 1] - A[i] - 1) / X);
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++)
    {
        if (v[i] <= 0)
        {
            continue;
        }
        if (K >= v[i])
        {
            K -= v[i];
        }
        else
        {
            res++;
        } 
    }
    cout << res << endl;
    return 0; 
}

Date June 21, 2021
Category Codeforces
Comments No Comments