ACM日常训练日记——7.26

• Atcoder训练
  1. Powerful Discount Tickets
     我们只需要动态维护使最大的值变小即可，这里我采用multiset去记录，有相同元素存在，也可以采用优先队列去维护

#include <bits/stdc++.h>

using namespace std;

using ll=long long;
ll n,m;
ll v[100010];
multiset<ll>st;
multiset<ll>::iterator ip;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>v[i],st.insert(v[i]);
	for(int i=1;i<=m;i++){
		ip = st.end();
		st.erase(--ip);
		st.insert(*ip/2);
	}
	ll ans=0;
	for(auto it=st.begin();it!=st.end();it++){
		ans+=*it;
	}
	cout<<ans;
}

2.Powerful Discount Tickets

• 动态规划专项训练
  1.方块与收纳盒
  这道题很像走楼梯问题，是一个经典的线性dp，楼梯每次只能走一楼和二楼，所以dp[i]=dp[i-1]+dp[i-2]的方案数
  这里也一样

#include <bits/stdc++.h>

using namespace std;
long long dp[1001];
int main(){
    int n;
    cin>>n;
    dp[1]=1;
    dp[2]=2;
    for(int i=3;i<=80;i++)dp[i]=dp[i-1]+dp[i-2];
   while(n--){
       long long t;
       cin>>t;
       cout<<dp[t]<<'\n';
   }
}

2.舔狗舔到最后一无所有
dp[i]代表前i天有多少种方案，分两种情况：(把问题转化成i和i-1不同，i和i-2不同)
1、第i天的饭菜与第i-2天的饭菜不同，那么前i天有dp[i-2]x2种方案2、第i天的饭菜与第i-1天的饭菜不同，那么前i天有dp[i-1]x2种方案
因此前i天共计dp[i-1]*2+dp[i-2]x2,在这中包含都不同的情况

#include <bits/stdc++.h>
#define size 100100
const int MOD=1e9+7;
using namespace std;
long long dp[size],n,m;
int main(){
    dp[1]=3,dp[2]=9;
    for (int i=3;i<size;i++){
        dp[i]=(dp[i-1]*2%MOD+dp[i-2]*2%MOD)%MOD;
    }
    scanf("%lld",&m);
    while (m--){
        scanf("%lld",&n);
        printf("%lld\n",dp[n]);
    }
    system("pause");
    return 0;
}

• Codeforcesz(Codeforces Round 962 (Div. 3))
  1.Left Right Operation
  送分题，如果能整除4，答案除4，不是的话加上1

#include <bits/stdc++.h>

using namespace std;

using ll=long long;

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	while(n--){
		ll t;
		cin>>t;
		if(t<=4)cout<<1<<'\n';
		else{
			if(t%4==0)cout<<t/4<<'\n';
			else cout<<t/4+1<<'\n';
		}
	}
}

2. Scale
继续送分，画图，它的图是以k个为单位画的，每次画加k即可

#include <bits/stdc++.h>

using namespace std;

using ll=long long;
int main() {
	
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		vector<string> grid(n);
		for (int i = 0; i < n; ++i) {
			cin >> grid[i];
		}
		int reduced_n = n / k;
		vector<string> reduced_grid(reduced_n, string(reduced_n, '0'));

		for (int i = 0; i < reduced_n; ++i) {
			for (int j = 0; j < reduced_n; ++j) {
		
				int start_row = i * k;
				int start_col = j * k;
			
				reduced_grid[i][j] = grid[start_row][start_col];
			}
		}
		for (int i = 0; i < reduced_n; ++i) {
			cout << reduced_grid[i] << '\n';
		}
	}
	return 0;
}

3.Sort
用二维前缀和来记录两个区间的字母数量和类型，然后进行判断大小，返回差值即可

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

vector<vector<int>> preprocess(const string& s) {
	int n = s.size();
	vector<vector<int>> prefix(26, vector<int>(n + 1, 0));
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 26; ++j) {
			prefix[j][i] = prefix[j][i - 1];
		}
		prefix[s[i - 1] - 'a'][i]++;
	}
	return prefix;
}

int mi(const vector<vector<int>>& prefix_a, const vector<vector<int>>& prefix_b, int l, int r) {
	int ans = 0;
	for (int i = 0; i < 26; ++i) {
		int ca = prefix_a[i][r] - prefix_a[i][l - 1];
		int cb = prefix_b[i][r] - prefix_b[i][l - 1]; // 修正这里的错误
		if (ca > cb) {
			ans += (ca - cb);
		}
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n, q;
		cin >> n >> q;
		string a, b;
		cin >> a >> b;
		
		vector<vector<int>> prefix_a = preprocess(a);
		vector<vector<int>> prefix_b = preprocess(b);
		
		for (int i = 0; i < q; ++i) {
			int l, r;
			cin >> l >> r;
			cout << mi(prefix_a, prefix_b, l, r) << '\n';
		}
	}
	return 0;
}

4.Fun
暴力加上减枝即可

#include <bits/stdc++.h>

using namespace std;

long long c(long long n, long long x) {
	long long count = 0;
	for (long long a = 1; a < x - 1; ++a) {
		for (long long b = 1; b < x - a; ++b) {
			long long ab = a * b;
			 if (ab >= n) break; // 如果 ab 已经大于等于 n，则不需要继续计算
			long long c1 = (a + b > 0) ? (n - ab) / (a + b) : 0;
			long long c2 = x - a - b;
			long long c_max = min(c1, c2);
			if (c_max > 0) {
				count += c_max;
			}
		}
	}
	return count;
}

int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;
	cin >> t;
	vector<long long> results;
	
	for (int i = 0; i < t; ++i) {
		long long n, x;
		cin >> n >> x;
		results.push_back(c(n, x));
	}
	
	for (long long result : results) {
		cout << result << '\n';
	}
	
	return 0;
}