暑假补题[6-30]（AtCoder)

三个数字，每次选择两个-1，或者全部-1，问最少多少次操作全是0.没法全是0就输出-1.
思路：
排序以后看差值就好了。

void solve()
{  
	ll a[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	if(a[2] - a[1] > a[0]){
		cout << -1 << endl;
	}
	else{
		cout << a[2] << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

B:

给你nn的矩阵，这个矩阵由1~nn组成且满足一个条件:每个格子的行都有一个比他小，每一列都有一个比他大。
思路：
总方案数-不合法方案
不合法的方案中， 不合法的格子(即既是一行中的最小又是一列中的最大)只会有一个， 那么我们可以枚举这个格子上的元素是什么， 把比它小的放在同一列， 比它大的放在同一行， 然后把其他的元素填在剩余的 （nn - (2 * n - 1)）个格子中就行了.
nn*C(i-1,n-1)C(n^{2-i,n-1)*(n-1)!*(n-1)!*(n}2-(2n-1))!.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define lowbit(x) (x&(-x))
const int N = 250005;
const ll mod = 998244353;
ll fac[N], inv[N];

inline ll power(ll a, ll b){
	ll res = 1;
	for(;b;b>>=1, a=1ll*a*a%mod)
		if(b&1)
			res = 1ll*res*a%mod;
	return res;
}

inline void prework(ll n){
	fac[0] = 1;
	for(ll i=1; i<=n; i++)
		fac[i] = 1ll*fac[i-1]*i%mod;
	inv[n] = power(fac[n], mod-2);
	for(ll i=n; i; i--)
		inv[i-1] = 1ll * inv[i] * i % mod;
}

inline ll C(ll n, ll m){
	return 1ll * fac[n] * inv[m] % mod * inv[n-m] % mod;
}

void solve(){
	ll n;
	cin >> n;
	prework(n * n);
	ll sum = fac[n * n]; 
	for(ll i = n; i <= n * (n - 1) + 1;i ++){
		sum = (sum - (n * n % mod * C(i - 1, n - 1) % mod * C(n * n - i, n - 1) % mod * fac[n - 1] % mod * fac[n - 1] % mod * fac[n * n - 2 * n + 1] % mod) % mod + mod) % mod;
		sum = (sum + mod) % mod;
	}
	cout << sum % mod << endl;
}

int main(){
	solve();
}
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

C:

void solve()
{
	cin >> n >> x >> y;
	for(int i=1; i<=n; i++){ 
		cin >> a[i], a[i] = a[i] % (x+y);
		if(a[i] < x){
			if(a[i] >= y) {
				cout << "Second" << endl;
				return;
			}
			else num ++;
		}
	}
	if(num == n){
		cout << "Second" << endl;
	}
	else cout << "First" << endl;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define lowbit(x) (x&(-x))
const int N = 2e5 + 100, M = N << 1;
int a[N], b[N];
int h[N], e[M], ne[M], w[M], id[M], idx;
int vis[N];
char ans[M];

void add(int a, int b, int c, int d){
	e[idx] = b, ne[idx] = h[a], w[idx] = c, id[idx] = d, h[a] = idx ++;
}

void dfs(int u)
{
	if(vis[u])return;
	vis[u] = 1;
	for(int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		if(ans[id[i]] == '?') 
			ans[id[i]] = '0' + w[i];
		dfs(j);
	}
}

void solve(){
	int n, m;
	cin >> n >> m;
	for(int i = 0; i <= n; i ++) h[i] = -1;
	for(int i = 0; i <= m; i ++) ans[i] = '?';
	for(int i = 1; i <= m; i ++)
	{
		cin >> a[i];
	}
	for(int i = 1; i <= m; i ++){
		cin >> b[i]; 
	}
	for(int i = 1; i <= m; i ++)
	{
		add(a[i], b[i], 1, i);
		add(b[i], a[i], 0, i);
	}
	for(int i = 1; i <= n; i ++){
		dfs(i);
	}
	for(int i = 1; i <= m; i ++){
		cout << ans[i];
	}
	cout << endl;
}

int main(){
	solve();
}
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
52
53
54
55
56
57
58