四川农业大学新生选拔赛

荷香竟深湎，永待盛夏陌。

先让1和4相同

再让143相同

再让最后再让143一起加到和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
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
64
65
66
67
68
69
70
71
72
73
#include<iostream>

#include<vector> 

using namespace std;

vector<int>ans(17);

int a[5];

int main(){

	int t;	cin>>t;

	while(t--){

		ans.clear();

		for(int i=1;i<=4;i++){

			cin>>a[i];

		}

		while (a[1] != a[4]){

        a[4] = a[4] % 4 + 1;

        a[2] = a[2] % 4 + 1;

        a[3] = a[3] % 4 + 1;

        ans.push_back(3);

    }

    while (a[4] != a[3]){

        a[1] = a[1] % 4 + 1;

        a[4] = a[4] % 4 + 1;

        a[2] = a[2] % 4 + 1;

        ans.push_back(1);

    }    

    while (a[1] != a[2]){

        a[4] = a[4] % 4 + 1;

        a[1] = a[1] % 4 + 1;

        a[3] = a[3] % 4 + 1;

        ans.push_back(4);

    }

		cout<<ans.size()<<endl;

		for(int i=0;i<ans.size();i++){

			cout<<ans[i]<<" ";

		}

		cout<<"\n";

	}

}

就算你是笨小猴我也爱你

洛谷一题改题面

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
#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
bool check(int x){
    if(x==1||x==0) return false;
    for(int i=2;i*i<=x;i++){
        if(x%i==0) return false;
    }
    return true;
}
void solve(){
    string s;
    cin>>s;
    map<char,int> mp;
    for(int i=0;i<s.length();i++){
        mp[s[i]]++;
    }
    int maxn=0,minn=1e9;
    for(auto [u,v]:mp){
        maxn=max(v,maxn);
        minn=min(v,minn);
    }
    if(check(maxn-minn)){
        cout<<"Lucky Word"<<'\n';
        cout<<maxn-minn<<'\n';
    }else{
        cout<<"No Answer"<<'\n';
        cout<<0<<'\n';
    }
}
int main(){
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

同余方程

扩展欧几里得求同余方程板子题

拓展欧几里得算法+线性同余方程 线性同余方程,也就是给定a,b,m,求一个整数x满足\(a \times x \equiv b(mod m)\),然后因为\(a \times x \equiv b(mod m)\)等价于\(a \times x-b\)是m的倍数,不妨设y为一个负数,那么这个方程可以改写为\(a \times x+m \times y=b\) 然后这道题目就是特殊的,\(a \times x \equiv 1 (mod b)\) 于是我们可以通过拓展欧几里得算法求出特解,然后\((x\%b+b)\%b\)来达到最小值的效果.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
 
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
 
int main()
{
    int a,b;
    cin>>a>>b;
    int x,y;
    int d=exgcd(a,b,x,y);
    cout<<(x%b+b)%b<<endl;
}

模板】01背包

题目描述

你有一个背包，最多能容纳的体积是V。

现在有n个物品，第i个物品的体积为vi,价值为wi

（1）求这个背包至多能装多大价值的物品？

（2）若背包恰好装满，求至多能装多大价值的物品？

输出描述:

1
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

本题有2个问，区别在于初值如何取。

  1. 如果不要求背包恰好装满，则无论如何都可以不放，因此数组初始化为0.
  2. 同时背包容量为0时，恰好装满等价于什么也不装，因此同时初始化dp[0]=0
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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1010;
const int INF = 0x3f3f3f3f;

int n, V, v[N], w[N], dp[N];

int main()
{

    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> V;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
    }

    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++)
        for (int j = V; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    cout << dp[V] << endl;

    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = V; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    if (dp[V] < 0) dp[V] = 0;
    cout << dp[V] << endl;
    return 0;
}

KMP最小循环节

给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少。

结论： n-next[n]

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define endl "\n"
#define PII pair<int,int>
const ll INF=0x3f3f3f3f;//3f3f3f3f;
const int mod=998244353;
const int N=1e6+5;
int ne[N];
void solve(){
    int n; cin>>n;
    string s; cin>>s;
    s=" "+s;
    for(int i=2,j=0;i<=n;i++){
        while(j&&s[i]!=s[j+1]) j=ne[j];
        if(s[i]==s[j+1]) j++;
        ne[i]=j;
    } cout<<n-ne[n]<<endl;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T=1; //cin>>T;
    while(T--) solve();
}

取石子游戏 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
const int M = 1e4;
int a[M], b[M];
 
void solve() {
    int n,k;
    cin >> n>>k;
    if(n%(k+1)==0)cout<<2;
    else cout<<1;
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    //cin>>t;
    while (t--)
        solve();
 
    return 0;
}