By

VP天梯赛

比赛时间3小时。

L1共100分，拿95分；

L2共100分，拿82分；

L3共90分，拿38分；

总共290分，拿199分。

因题目难度原因，部分题目不列举。

L1-6 这不是字符串题

大模拟，不知为啥一个测试点错误一个测试点段错误。

我采用vector只能拿10分，知乎大佬采用string能拿满。

#include <bits/stdc++.h>
using namespace std;
void solve(){
	int n,m;cin>>n>>m;
	string s;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		s.push_back(char('a'+x-1));
	}
	while(m--){
		int op;cin>>op;
		if(op==1){
			int x;cin>>x;
			int len=x;
			string t;
			while(x--){
				int k;cin>>k;
				t.push_back(char('a'+k-1));
			}
			int x2;cin>>x2;
			int len2=x2;
			string t2;
			while(x2--){
				int k;cin>>k;
				t2.push_back(char('a'+k-1));
			}
			if(s.find(t)==string::npos){
				continue;
			}else{
				s.replace(s.find(t),len,t2);
			}
		}else if(op==2){
			string ne;
			for(int i=0;i<s.length()-1;i++){
				int x1=s[i]-'a'+1,x2=s[i+1]-'a'+1;
				if((x1+x2)%2==0){
					ne.push_back(s[i]);
					ne.push_back(char((x1+x2)/2+'a'-1));
				}else{
					ne.push_back(s[i]);
				}
			}
			ne.push_back(s.back());
			s=ne;
		}else{
			int l,r;cin>>l>>r;
			l--;
			reverse(s.begin()+l,s.begin()+r);
		}
	}
	for(int i=0;i<s.length();i++){
		int x=(s[i]-'a'+1);
		if(i!=s.length()-1) cout<<x<<" ";
		else cout<<x;
	}
}
int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t=1;
	while(t--) solve();
	return 0;
}

L1-7 大幂数

从最大幂次开始往下遍历。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll n;
	cin>>n;
	ll x=log2(n);
	for(int i=x;i>=1;i--){
		ll sum=0;
		ll y=1,z=0;
		while(sum<n){
			sum+=pow(y,i);
			y++;
		}
		if(sum==n){
			for(int j=1;j<y;j++){
				cout<<j<<'^'<<i;
				if(j!=y-1) cout<<'+';
			}
			return 0;
		}
	}
	cout<<"Impossible for "<<n<<".";
	return 0;
}

L1-8 现代战争

又是模拟，采用map或数组存储哪些行和列没有，采用优先队列快速按大小取值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,xlen,ylen;
struct nod{
	int zhi;
	int x;
	int y;
	friend bool operator <(nod a,nod b){
		return a.zhi<b.zhi;
	}
}a[1001][1001];
map<int,bool> mpx,mpy;
priority_queue<nod> pq;
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j].zhi;
			a[i][j].x=i;
			a[i][j].y=j;
			pq.push(a[i][j]);
		}
	}
	while(k--){
		nod z=pq.top();pq.pop();
		while(!(mpx[z.x]==0&&mpy[z.y]==0)&&!pq.empty()){
			z=pq.top();pq.pop();
		}
		mpx[z.x]=1,mpy[z.y]=1;
		xlen++,ylen++;
	}
	int xx=0,yy=0;
	for(int i=1;i<=n;i++){
		if(mpx[i]==1) continue;
		yy=0;
		for(int j=1;j<=m;j++){
			if(mpy[j]==1) continue;
			cout<<a[i][j].zhi;
			yy++;
			if(yy!=m-ylen) cout<<" ";
		}
		cout<<"\n";
	}
	return 0;
}

L2-1 算式拆解

典。关于算式运算采用stack可简单快速。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s,str;
stack<string> st;
int a,b=1;
int main(){
	cin>>s;
	int i=0;
	str="";
	for(int i=0;i<s.size();i++){
		if(s[i]=='('){
			if(str!=""){
				st.push(str);
				str="";
			}
			a++;
			st.push("(");
		}else if(s[i]!=')'){
			str+=s[i];
		}else{
			if(str!=""){
				st.push(str);
				str="";
			}
			cout<<st.top();
            cout<<"\n";
			b=1;
			st.pop();st.pop();
		}
	}
	return 0;
}

L2-2 三点共线

此题25分赶时间我只拿了16分走人。

知乎大佬题解：

枚举 $y=0$ 和 $y=1$ 时的 $x$，再用 bitset 维护 $y=2$ 时的 $x$ 即可。

和我思路一样，我没去重并且采用unordered_map维护。

const int N = 8e6 + 7;
const int d = 4e6; // 这里把所有点都向右移动4e6即可保证不会出现负数
vector<int> a[2];
bitset<N> pos;
void solve(){
    int n; cin >> n;
    rep(i, 1, n) {
        int x, y; cin >> x >> y;
        if(y < 2) a[y].push_back(x);
        else pos[x + d] = true;
    }
    rep(i, 0, 2) sort(all(a[i]));
    rep(i, 0, 2) a[i].erase(unique(all(a[i])),a[i].end());
    vector<pii> ans;
    for(int &x0 : a[0]) {
        for(int &x1 : a[1]) {
            int x2 = x1 * 2 - x0;
            if(pos[x2 + d]) ans.push_back({x1, x0});
        }
    }
    sort(all(ans));
    if(!ans.empty()) {
        for(auto &[x1, x0] : ans) {
            int x2 = x1 * 2 - x0;
            cout << '[' << x0 << ", 0] [" << x1 << ", 1] [" << x2 << ", 2]\n";
        }
    } else cout << -1;
}

L2-3 胖达的山头

前缀和基础题。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int l,r,l1,r1;
map<int,int> mp;
int sum[100000];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int a,b,c;
		scanf("%d:%d:%d",&a,&b,&c);
		l=a*60*60+b*60+c;
		scanf("%d:%d:%d",&a,&b,&c);
		r=a*60*60+b*60+c;
		sum[l]++;sum[r+1]--;
	}
	int ans=0;
	for(int i=1;i<=86400;i++){
		sum[i]+=sum[i-1];
		ans=max(sum[i],ans);
	}
	cout<<ans;
	return 0;
}

L2-4 被n整除的n位数

25分拿了16分走人。

知乎大佬题解：

直接暴搜！

我还利用性质花费大量时间拿16分，成nt了

ll n, a, b;
bool f = true;
void dfs(ll x, int dep) {
	if(dep == n) {
		if(x >= a && x <= b) {
			cout << x << '\n';
			f = false;
		}
		return;
	}
	rep(i, 0, 9) {
		if((x * 10 + i) % (dep + 1)) continue;
		dfs(x * 10 + i, dep + 1);
	}
}
void solve(){
	cin >> n >> a >> b;
	int st = to_string(a)[0] - '0', ed = to_string(b)[0] - '0';
	rep(i, st, ed) dfs(i, 1);
	if(f) cout << "No Solution";
}

L3-1 人生就像一场旅行

时间不够了，想dfs拿点分，但题目都还没读明白。

知乎大佬题解：

点的个数为500，没给边的数量，为完全图时会卡掉 Dijkstra。可以用 Floyd 解决此问题。

先走花费最小的点，如果有多个花费最小的点再选沿途心情指数最高的点。天梯赛以前有道思想一模一样的题。L2-001 紧急救援

好吧，我对于最短路算法全部还给教练了。

const int inf = 1e9; // 防止爆int
const int N = 5e2 + 7;
int d[N][N], h[N][N];
void Solution(){
	int b, n, m, k; cin >> b >> n >> m >> k;
	rep(i, 1, n) rep(j, 1, n) d[i][j] = inf; // Floyd初始化
	rep(i, 1, n) d[i][i] = 0;
	rep(i, 1, m) {
		int x, y, u, v; cin >> x >> y >> u >> v;
		d[y][x] = d[x][y] = min(d[x][y], u); // 处理重边
		h[y][x] = h[x][y] = max(h[x][y], v);
	}
	rep(k, 1, n) rep(i, 1, n) rep(j, 1, n) { // Floyd
		if(d[i][j] == d[i][k] + d[k][j]) {
			h[i][j] = max(h[i][j], h[i][k] + h[k][j]);
		} else if(d[i][j] > d[i][k] + d[k][j]) {
			d[i][j] = d[i][k] + d[k][j];
			h[i][j] = h[i][k] + h[k][j];
		}
	}
	while(k --) {   // 处理询问
		int x; cin >> x;
		vector<int> ans;
		rep(y, 1, n) {
			if(y == x || d[x][y] > b) continue;
			if(ans.size()) cout << ' ';
			cout << y;
			ans.push_back(y);
		}
		if(ans.empty()) {
			cout << "T_T\n";
			continue;
		} else cout << '\n';
		int hmax = 0;
		for(auto &y : ans) hmax = max(hmax, h[x][y]);
		bool f = false;
		for(auto &y : ans) {
			if(h[x][y] != hmax) continue;
			if(f) cout << ' ';
			cout << y;
			f = true;
		}
		cout << '\n';
	}
}

L3-2 影响力

暴力拿了20分，总分30。

知乎大佬题解：

拆成八个方向分别算，

采用递推。$(i,j)$左上方（不含正上正左）的距离和=$(i-1,j-1)$左上方（含正上正左）的距离和+$(i,j)$左上方的方格数量。

似乎也可以说是一个DP。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cal(int i){
	return (i*(i+1ll)/2);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;cin>>n>>m;;
	vector<vector<ll> > pre(n,vector<ll>(m,0));
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			pre[i][j]=cal(i)+cal(j);
			if(i&&j) pre[i][j]+=pre[i-1][j-1]+1ll*i*j;
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			ll x;cin>>x;
			cout << x * (pre[i][j] + pre[n - 1 - i][j] + pre[i][m - 1 - j] + pre[n - 1 - i][m - 1 - j] - cal(j) - cal(m - 1 - j) - cal(i) - cal(n - 1 - i)) << " \n"[j == m - 1];
		}
	}
	return 0;
}

L3-042 污染大亨

没找到AC题解，只有暴力dfs16分。

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define int long long 
#define double long double
#define _rep(i,a,b) for(int i=(int)(a);i<=(int)b;++i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define pp pop_back()
#define fi first
#define se second
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
int n,m,k;
const int N=1e6+10,INF=4e18,P=998244353;
vector<vector<int>>v(N);
int c[N];
int st[N];
int sum;
int qmi(int a,int b,int P){
	int res=1;
	while(b){
		if(b&1)res=res*a%P;
		a=a*a%P;
		b>>=1;
	}
	return res;
}
void infact(int u){
	sum++;
	st[u]++;
	for(auto i:v[u]){
		infact(i);
	}
	return;
}
void finfact(int u){
	st[u]--;
	for(auto i:v[u]){
		finfact(i);
	}
	return;
}
int res=0;
void dfs(int u,vector<int>&ve,int now){
	bool bl=false;
	_rep(i,1,n){
		if(st[i])continue;
		bl=true;
		sum=0;
		infact(i);
		dfs(u+1,ve,now*qmi(c[u],sum,P)%P);
		finfact(i);
	}
	if(!bl)res+=now,res%=P;
}
void solve(){
	cin>>n;
  	_rep(i,2,n){
		int x;
		cin>>x;
		v[x].pb(i);
	}
	_rep(i,1,n)cin>>c[i];
	vector<int>ve;
	dfs(1,ve,1);
	cout<<res;
}
signed main(){
	IOS;
	int T=1;
	while(T--)
		solve();
	return 0;
}