A Gift Carpet

模拟，按列遍历一个一个选

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
#include<bits/stdc++.h>
using namespace std;
const string s = "vika";
void solve()
{
	int n, m;
    cin >> n >> m;
    vector<string> g(m);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            char c;
            cin >> c;
            g[j] += c;
        }
    }
    int ans = 0;
    for(int i = 0; i < m && ans != 4; i++){
        if (g[i].find(s[ans]) != string::npos){
            ans++;
        }
    }
    cout << (ans == 4 ? "Yes" : "No") << '\n';
}

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int T;
	cin >> T;
	while(T -- ) solve();
	return 0;
}

B Sequence Game

感觉随便构造都能过

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
#include<bits/stdc++.h>
using namespace std;

void solve()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i ++ ) cin >> a[i];
	vector<int> ans;
	ans.emplace_back(a[0]);
	for(int i = 1; i < n; i++)
	{
		if(a[i] < ans.back()) ans.push_back(a[i]); 
		ans.push_back(a[i]);
	}
	cout << ans.size() << '\n';
	for(int i = 0; i < ans.size(); i ++ ) cout << ans[i] << " \n"[i == ans.size() - 1];
}

int main()
{
	int T;
	cin >> T;
	while(T -- ) solve();
	return 0;
}

C Flower City Fence

水平来看，相当于区间修改，直接差分，最后求和和原数组对比

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
#include<bits/stdc++.h>
using namespace std;

void solve()
{
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for(int i = 1; i <= n; i++) cin >> a[i];
	if(a[1] != n) 
	{
		cout << "NO\n";
		return;
	}
	vector<int> b(n + 2);
	for(int i = 1; i <= n; i++)
	{
		b[1]++, b[a[i] + 1]--;
	}
	for(int i = 1; i <= n; i++)
	{
		b[i] += b[i - 1];
		if(a[i] != b[i])
		{
			cout << "NO\n";
			return;
		}
	}
	cout << "YES\n";
}

int main()
{
	int T;
	cin >> T;
	while(T -- ) solve();
	return 0;
}

D Ice Cream Balls

优先选不同的数字，得到的结果最多，设种类为m，结果为$m * (m - 1) / 2$，二分找到第一个结果数大于等于n的m，如果刚好等于则输出m，如果大于，则说明有m - 1个不同的，剩下的组合则是又相同的种类构成，共$n - (m - 1) * (m - 2) / 2$，所有一个有$m - 1 + n - (m - 1) * (m - 2) / 2$个

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
	int n;
	cin >> n;
	int l = 1, r = 1e10;
	while(l < r)
	{
		int mid = (l + r) >> 1;
		
		if(mid * (mid - 1) / 2 >= n ) r = mid;
		else l = mid + 1;
	}
	if(l * (l - 1) / 2 == n) cout << l << '\n';
	else
	{
		int res = l - 1 + n - (l - 1) * (l - 2) / 2;
		cout << res << '\n';
	}
}

signed main()
{
	int T;
	cin >> T;
	while(T -- ) solve();
	return 0;
}

E Kolya and Movie Theatre

首先负数我们肯定不看，手模两个数据可以发现，假如你最后一个观看的电影在第$x$天，不管你前面怎么看总共都要减去x * d，这样的话，对于第x天是最后一天这种情况，最大的可能只会是观看前x天最大的m个，那我们可以用一个堆维护前i个里面最大的m个，并记录总和，枚举x

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
	int n, m, d;
	cin >> n >> m >> d;
	int sum = 0, res = 0;
	priority_queue<int,vector<int>,greater<int>> heap;
	for(int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		if(x > 0)
		{
			heap.push(x);
			sum += x;
		}
		if(heap.size() > m)
		{
			sum -= heap.top();
			heap.pop();
		}
		res = max(res, sum - i * d);
	}
	cout << res << '\n';
}

signed main()
{
	int T;
	cin >> T;
	while(T -- ) solve();
	return 0;
}

F Magic Will Save the World

看了看样例解释，我们攒魔力，最后一口气消灭全部怪物，全部怪物血量总和为sum，假设水魔法总共消灭了总计血量x的怪物，那么消耗的时间因为$min(x/w, (sum - x) / f)$，所有我们枚举水魔法消灭多少就行。如何求出水魔法可以消灭怪物的所有可能？典型01背包

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
	int w, f;
	cin >> w >> f;
	int n;
	cin >> n;
	vector<int> a(n + 1);
	int sum = 0;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		sum += a[i];
	}
	vector<int> dp(sum + 10);
	dp[0] = 1;
	int res = 1e12;
	for(int i = 0; i < n; i++)
	{
		for(int j = sum; j >= a[i]; j--)
		{
			dp[j] = dp[j] || dp[j - a[i]];
		}
	}
	int cnt = 0;
	for(int i = 0; i <= sum; i++)
	{
		if(dp[i])
		{
			res = min(res, max((int)ceil(1.0*i/w),(int)ceil(1.0*(sum-i)/f)));
		}
	}
	cout << res << endl;

}

signed main()
{
	int T;
	cin >> T;
	while(T -- ) solve();
	return 0;
}

G The Great Equalizer (没懂)