浙江机电职业技术学院新生赛

img

浙江机电职业技术学院第八届新生亮相赛

小王的魔法

直接让因字数全部填满

就是这样子的公式

#include <iostream>
 
using namespace std;
 
int main(){
    long long n;
    cin>>n;
     
    cout<<(n+1)/2<<endl;
     
    return 0;
}

苏神的遗憾

特判一下，满足一定互不相等

# include <iostream>
# include<algorithm>
using namespace std;
int main() {
    long long n;
    cin >> n;
    long long a[1000000];
    for (long long i = 1;i <= n;i++)
        cin >> a[i];
    sort(a+1, a+n+1);
if(a[2]-1>a[1])
    cout << a[2] - 1 << endl;
if(a[2]-1==a[1])
    cout <<a[1]-1<<endl;
    return 0;
 
}

吝啬的拒绝

Floyd即可

#include <bits/stdc++.h>
using namespace std;
int i,j,k,n,m,t,f[805][805],res;
vector<int>v;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>t;
    while(n--)
    {
        cin>>k; 
        v.push_back(k);
    }
    memset(f,0x3f,sizeof(f));
    for(i=1;i<=m;i++) f[i][i]=0;
    while(t--)
    {
        cin>>i>>j>>k;
        f[i][j]=f[j][i]=min(f[i][j],k);
    }
    for(i=1;i<=m;i++) for(j=1;j<=m;j++) for(k=1;k<=m;k++)
    f[j][k]=min(f[j][k],f[j][i]+f[i][k]);
    res=1e9;
    for(t=1;t<=m;t++)
    {
        k=0;
        for(auto i:v) k+=f[i][t];
        res=min(res,k);
    }
    cout<<res;
}

山里灵活

#include <bits/stdc++.h>
using namespace std;
    
    
int main(){
    int t;
    long long n,k;
    cin>>t;    
    while(t--)
    {       
        cin>>n>>k;
        if(n*10>=90*7*k){
            cout<<"SHENLILINHUA WO LAI LA!!!"<<endl;
        }else{
            cout<<"SHENLILINHUA DENG DENG WO!!!"<<endl;
        }
    }
        
    return 0;
}

数列排序

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
const int N = 1e6 + 100;
int a[N];
int num[N];
int main()
{
int  n;
cin>>n;
rep(i,1,n)
{
    cin>>a[i];
    num[i]=a[i];
}
sort(a+1,a+1+n);
rep(i,1,n)
{
    num[i]=lower_bound(a+1,a+1+n,num[i])-a;
}
int ans=0;
rep(i,1,n)
{
    while(num[i]!=i)
    {
        swap(num[i],num[num[i]]);
        ans++;
    }
}
cout<<ans<<'\n';

}

一种很新的阶乘

欧拉函数求解质因数

#include <bits/stdc++.h>
using namespace std;
long long cnt[10000001];
void print(int a, long long b) {
	cout << a;
	if (b > 1) {
		cout << "^" << b;
	}
}
vector<int> prime;
int vis[10000001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int x;
	cin >> x;
	for (int i = 2 ; i <= x ; i++) {
		if (vis[i] == 0) {
			vis[i] = i;
			prime.emplace_back(i);
		}
		for (int j = 0 ; j < int(prime.size()) && 1LL * i * prime[j] <= x ; j++) {
			vis[i * prime[j]] = prime[j];
			if (i % prime[j] == 0) {
				break;
			}
		}
	}
	for (int i = 1 ; i < x ; i++) {
		int k = x - i + 1;
		cnt[k] += i;
		if (vis[k] == k) continue;
		int z1 = vis[k], z2 = k / vis[k];
		cnt[z1] += cnt[k];
		cnt[z2] += cnt[k];
		cnt[k] = 0;
	}
	cout << "f(" << x << ")=";
	bool flag = false;
	for (int i = 1 ; i <= x ; i++) {
		if (cnt[i] != 0) {
			if (flag) {
				cout << "*";
			}
			print(i, cnt[i]);
			flag = true;
		}
	}
	return 0;
}

自由还是爱情 这是个问题

两次01背包

#include <bits/stdc++.h>
using namespace std;
int dp[2][2005];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, k;
	cin >> n >> k;
	for (int i = 0 ; i <= 2000 ; i++) 
    {
		dp[0][i] = dp[1][i] = 20000;
	}
	dp[0][0] = dp[1][0] = 0;
	for (int i = 1 ; i <= n ; i++) 
    {
		int x, y, z;
		cin >> x >> y >> z;
		for (int j = 2000 ; j >= z ; j--) {
			dp[x][j] = min(dp[x][j], dp[x][j - z] + y);
		}
	}
	int mx[2] = {};
	for (int i = 2000 ; i >= 0 ; i--) {
		if (dp[0][i] <= k) 
        {
			mx[0] = max(mx[0], i);
		}
		if (dp[1][i] <= k) {
			mx[1] = max(mx[1], i);
		}
	}
	if (mx[0] >= mx[1]) {
		cout << mx[0] << " " << 0;
	} else {
		cout << mx[1] << " " << 1;
	}
	return 0;
}

基本操作

#include <bits/stdc++.h>
using namespace std;

// 2023 OneWan

void solve() {
	int n, m;
	cin >> n >> m;
	string str;
	cin >> str;
	str = " " + str;
	string cx = "";
	for (int i = 0 ; i < m ; i++) {
		string s;
		cin >> s;
		if (s == "cc") {
			int L, R;
			cin >> L >> R;
			cx = str.substr(L, R - L + 1);
		} else if (s == "cv") {
			int pos;
			cin >> pos;
			if (cx != "") {
				str.insert(pos + 1, cx);
			}
		} else {
			int L, R;
			cin >> L >> R;
			cx = str.substr(L, R - L + 1);
			str.erase(begin(str) + L, begin(str) + R + 1);
		}
	}
	cout << str.substr(1) << "\n";
}

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

夜雷の史莱姆农场

#include <bits/stdc++.h>
using namespace std;

// 2023 OneWan

long long qpow(long long a, long long b, long long p) {
	long long res = 1;
	while (b) {
		if (b & 1) {
			res = res * a % p;
		}
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

void solve() {
	long long a, b, p;
	cin >> a >> b >> p;
	cout << qpow(a, b, p) << "\n";
}

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

小黑屋查的救赎

BFS

#include <bits/stdc++.h>
using namespace std;

int n, m, p, k;
char g[11][11];
int sx, sy, ex, ey;
int dist[11][11][101];

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> p >> k;
	for (int i = 1 ; i <= n ; i++) {
		for (int j = 1 ; j <= m ; j++) {
			cin >> g[i][j];
			if (g[i][j] == 's') {
				sx = i;
				sy = j;
			}
			if (g[i][j] == 'e') {
				ex = i;
				ey = j;
			}
			for (int z = 0 ; z <= k ; z++) {
				dist[i][j][z] = 1000;
			}
		}
	}
	queue<pair<int, int>> que;
	que.emplace(sx, sy);
	dist[sx][sy][k] = 0;
	int temp = 0;
	while (!que.empty()) {
		temp++;
		auto [x, y] = que.front();
		que.pop();
		for (int i = 0 ; i < 4 ; i++) {
			int xx = x + dx[i], yy = y + dy[i];
			if (xx < 1 || xx > n || yy < 1 || yy > m) {
				continue;
			}
			if (g[xx][yy] == 'w') continue;
			bool flag = false;
			for (int j = 0 ; j <= k ; j++) {
				if (j - (g[xx][yy] == 'd') >= 0 && dist[xx][yy][j - (g[xx][yy] == 'd')] > dist[x][y][j] + 1) {
					dist[xx][yy][j - (g[xx][yy] == 'd')] = dist[x][y][j] + 1;
					flag = true;
				}
			}
			if (flag) {
				que.emplace(xx, yy);
			}
		}
	}
	for (int i = 0 ; i <= k ; i++) {
		if (dist[ex][ey][i] <= p) {
			cout << "YES";
			return 0;
		}
	}
	cout << "NO";
	return 0;
}

兔子不会种树

预处理加二分

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int k, n;
	cin >> k >> n;
	vector<__int128> ans;
	__int128 r = 1, sum = r;
	while (k != 1 && sum <= 1000000000000000000LL) {
		ans.emplace_back(sum);
		r *= k;
		sum += r;
	}
	for (int i = 1 ; i <= n ; i++) {
		long long x;
		cin >> x;
		if (k == 1) cout << x - 1 << "\n";
		else cout << (lower_bound(begin(ans), end(ans), x) - begin(ans)) << "\n";
	}
	return 0;
}

淘金币

我们可以先观察一些变换的发生，发生1变换是把A变没在B后加一个C，但是C又没用，B是一直存在的，但是后面有了C这个B就不能进行任何变换，但是我们可以发现这个B还可以去跟前面的A变换再生成BC。变换2则是与它相反。 我们可以想到1.当开头或结尾存在至少一个B就一定可以把所有的A都合并完，得到的金币数也就是A的个数，当有两个B连在一块时也可以把所有的A都合并完，一个向前一个向后。当这两种情况都不存在时，就是这种AABABAA这些B把A分成了B的个数+1个区间，我们的Ｂ只有向一个方向合并，所以我们只能舍去一个区间，要想合并次数最多，我们只能舍去一个最小Ａ的区间，所以这种情况直接去找Ａ个数最少的一段，用总的Ａ的个数减去这一段就行了

#include <bits/stdc++.h>
typedef long long ll; 
typedef std::pair<int,int> PII;
typedef std::pair<ll,ll> PLL;
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define CTN continue
#define MEM(a,b) memset(a,b,sizeof (a) );
#define _for(i,a,b) for(int i=a,I_MAX=b;i<=I_MAX;i++)
#define _rep(i,a,b) for(int i=a,I_MIN=b;i>=I_MIN;i--)
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N=2e5+10;
using namespace std;

int n,a,b,min_=1e9,cnt,ad;
string s;
int main() {
    FIO;
    cin>>n;
    while(n--)
    {
        a=0,b=0,ad=0,min_=1e9,cnt=0;
        cin>>s;
        s+='B';
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='A')
            {
                cnt++;
                a++;
            }
            else 
            {
                b++;
                if(cnt!=0)
                {
                    ad++;
                    min_=min(min_,cnt);
                    cnt=0;
                }
            }
        }
        b--;
        if(b>=ad)
        cout<<a<<endl;
        else
        cout<<a-min_<<endl;
    }
    
}

兔子饼干

#include <bits/stdc++.h>
using namespace std;

// 2023 OneWan

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	while (cin >> n) {
		if (n == 1) {
			cout << "就这？就这？\n";
		} else {
			cout << "哼！哼！啊啊啊啊啊啊！\n";
		}
	}
	return 0;
}