听说是队长 WongDark 出的题😱，emmmm 好简单？？😰

7-1.简单数学题

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;

signed main()
{
	long long a,b;
	cin>>a>>b;
	cout<<__gcd(a,b)<<endl;
	return 0;
}

7-2.拿子游戏

思路：巴什博奕——对于当前局势的可以取的 n , m 来说 n %(m+1)== 0 后手必胜，否则先手必胜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;cin>>t;
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n % (m+1) !=0) printf("yE5\n");
        else printf("n0\n");
    }
    return  0;
}

7-3.数塔问题

题意：如下图所示为一个数塔，从数塔的顶层出发，在每一个结点可以选择向左走或者向右走，一直走到最底层。要求找出一条路径，使得路径上的数值和最大。

上图所示的数塔中，最大路径和为 1+2+3+2+1=9

思路：经典数塔问题，区别在于这个做了一个变式还有 n-1 层的递减，只需要处理好由下向上的转移方程就可以了

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

int n;
ll dp[505][505];

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=i;++j)
            cin>>dp[i][j];
    for(int i=n+1;i<=2*n-1;++i)
        for(int j=1;j<=2*n-i;++j)
            cin>>dp[i][j];
    for(int i=2*n-2;i>=n;--i)
        for(int j=1;j<=2*n-i;++j)
            dp[i][j]+=max(dp[i+1][j-1],dp[i+1][j]);
    for(int i=n-1;i>=1;--i)
        for(int j=1;j<=i;++j)
            dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
    cout<<dp[1][1]<<endl;
    return 0;
}

7-4.飞机探测

思路：洛谷变式题，分治法经典题

7-5.王的疑惑

题意：国王想要修路使任意两个城市都可以互相到达（可以直接也可以间接），国王希望修建的道路尽可能的少，请回答他修路的最高花费和最低花费的差值

思路：就是求最大生成树和最小生成树的权值和之差

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
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int fa[200005];//父元素数组

struct node{
	int x,y,v;
}road[500005];//路的条数大概是最多不超过m

bool cmp1(node x,node y){//比较声明，按升序排列
	return x.v<y.v;
}

bool cmp2(node x,node y){//比较声明，按升序排列
	return x.v>y.v;
}

void init(){
	for(int i=1;i<=n;i++)
	fa[i]=i;
}

int find(int x){//压缩路径的三目运算符
	return fa[x]==x?x:fa[x]=find(fa[x]);
}

void join(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx==fy)
	return;
	else{
		fa[fy]=fx;
	}
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	while(cin>>n>>m){
		init();//初始化
		for(int i=1;i<=m;i++)
		cin>>road[i].x>>road[i].y>>road[i].v;
		sort(road+1,road+1+m,cmp1);//对权值升序排序 
		int sum1=0,sum2=0;
		for(int i=1;i<=m;i++){
			if(find(road[i].x)!=find(road[i].y)){//找到没有通路的两点 
				sum1+=road[i].v;//加和
				join(road[i].x,road[i].y);//连接
			}
		}
		init();
        sort(road+1,road+m+1,cmp2);
        for(int i=1;i<=m;i++){
			if(find(road[i].x)!=find(road[i].y)){//找到没有通路的两点 
				sum2+=road[i].v;//加和
				join(road[i].x,road[i].y);//连接
			}
		}
        cout<<sum2-sum1<<endl;
	}
	return 0;
}

7.6-任务分配

思路：因为数据很小所以可以直接搜索，保证在矩阵中选的 n 个元素任意两个没有处于同一行（一个任务只能分配给一个人）或者同一列（一个人只能被分配一个任务）即可。但是需要剪枝：一是维护一个最小值 minn 每次搜索过程中就超过最小值没必要继续当前的搜索，其次还需要再进行一个剪枝就是维护每个任务的分配最小值的后缀和，当后面没搜索的加上这个后缀和都大于 minn 那也没必要继续当前搜索了

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;
typedef long long ll;

int n;
int ans;
int m[25][25];
bool vis[25];
int minn[25];

void dfs(int step, int cost) {
    if (step >= n + 1) {
        ans = min(ans, cost);
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (vis[i] == 0) {
            if (m[step][i] + cost >= ans) continue;                   //剪枝1
            if (m[step][i] + cost + minn[step + 1] >= ans) continue;  //剪枝2
            vis[i] = 1;
            dfs(step + 1, m[step][i] + cost);
            vis[i] = 0;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= n; ++j) 
            cin >> m[i][j];
    for(int i=n;i>=1;--i){
        int p=0x3f3f3f3f;
        for(int j=1;j<=n;++j){
            p=min(p,m[i][j]);
        }
        minn[i]+=minn[i+1]+p; //从i~n行全取最小值的后缀和
    }
    ans = 0x3f3f3f3f;
    dfs(1, 0);
    cout << ans << endl;

    return 0;
}

7-7.国王的奖励

题意：求一个等比数列 qn 的和，由于结果可能很大最后对 1e8+7 取模

思路：

  1. 当 q==1 时就是 n 个 1 相加，但是注意 n 的数据范围，答案也需要取模

  2. 当 q!=1 时利用求和公式，但是由于需要取模（除法不满足模运算），利用逆元将公式转换为乘法

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 100000007;

inline ll read() {
    ll s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}

ll quick_pow(ll a, ll b) {  //矩阵快速幂
    ll res = 1, base = a % mod;
    while (b) {
        if (b & 1)
            res = (base * res) % mod;
        base = (base * base) % mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll a) {
    return quick_pow(a, mod - 2) % mod;  //欧拉定理求逆元
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    t = read();
    while (t--) {
        ll q, n;
        q = read(), n = read();
        if (q == 1) {
            cout << n % mod << endl;
            continue;
        }
        q %= mod;
        ll a = quick_pow(q, n) % mod;
        cout << (((a - 1) % mod) * (inv(q - 1) % mod)) % mod << endl;
    }
    return 0;
}

7-8.起泡排序

思路：冒泡排序本质是大小逆序的数交换，所以得到最终结果一定是每个逆序对都发生了交换。那么这题饶了半天就是让我们求一下这个序列的逆序数和，由于元素范围很大还需要利用一下离散化。求逆序数可以用树状数组或者权值线段树

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+5;

int n;
int a[maxn];//离散化后的数组
int c[maxn];//树状数组

struct node{
	int val,id;
}in[maxn];

int lowbit(int i){
	return i&(-i);
}

void update(int i,int k){
	while(i<=n){
		c[i]+=k;
		i+=lowbit(i);
	}
}

int getsum(int i){
	int res=0;
	while(i>0){
		res+=c[i];
		i-=lowbit(i);
	}
	return res;
}

bool cmp(node a,node b){
	return a.val<b.val;
}

signed main(){
	while(cin>>n&&n){
		//离散化
		for(int i=1;i<=n;i++){
			cin>>in[i].val;
			in[i].id=i;
		}
		sort(in+1,in+n+1,cmp);
		for(int i=1;i<=n;i++)
		a[in[i].id]=i;
		//树状数组求逆序
		memset(c,0,sizeof(c));
		long long ans=0;//要是处理很多数，即使离散化了也很可能超出int范围
		for(int i=1;i<=n;i++){
			update(a[i],1);//1代表该位置数存在
			ans+=i-getsum(a[i]);
		}
		cout<<ans<<endl; 
	}
	return 0;
}

7.9大师的比试

思路：经典贪心题，为了在固定的时间内多比几场所以将时间段的结束时间从早到晚排序。当时间段的结束时间相同时，为了避免时间段重叠所以将时间段的开始时间从晚到早排序，然后按照排好序的时间走一遍统计能进行的比试。同时因为数据范围太大只能用 string 存储还需要写一个大数比较的函数

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
//也可以写重载运算符但是不会
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;

struct node {
    string l, r;
} m[10005];

bool cal(string a, string b) {  //小于返还1，大于返还0
    int lena = a.length(), lenb = b.length();
    if (lena != lenb) return lena < lenb;
    for (int i = 0; i < min(lena, lenb); ++i) {
        if (a[i] == b[i])
            continue;
        else
            return a[i] < b[i];
    }
    return 1;
}

bool cmp(node a, node b) {  //从小到大排序
    if (a.r != b.r)
        return cal(a.r, b.r);
    return cal(b.l, a.l);
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> m[i].l >> m[i].r;
    sort(m + 1, m + 1 + n, cmp);
    int cnt = 0;
    string t = "0";
    for (int i = 1; i <= n; ++i) {
        if (cal(t, m[i].l)) {
            ++cnt;
            t = m[i].r;
        }
    }
    cout << cnt << endl;
    return 0;
}