专栏文章

2025寒假专场7

ccompaq
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqhjoal
此快照首次捕获于
2025/12/04 04:54
3 个月前
此快照最后确认于
2025/12/04 04:54
3 个月前
查看原文
回文字符串
入门模拟
重叠薄片
模拟，枚举A和B的相对位置，然后与C进行匹配
CPP

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

 
int ha,hb,hc,wa,wb,wc;
int a[15][15], b[15][15], c[35][35];
int ans[35][35];
char s[15];
 
 
int main(){
    cin >> ha >> wa;
    for(int i = 1;i <= ha; i ++ ){
        cin >> (s + 1);
        for(int j = 1;j <= wa; j ++ )
            a[i][j] = (s[j] == '#');
    }
    cin >> hb >> wb;
    for(int i = 1;i <= hb; i ++ ){
        cin >> (s + 1);
        for(int j = 1;j <= wb; j ++ )
            b[i][j] = (s[j] == '#');
    }
    cin >> hc >> wc;
    for(int i = 1;i <= hc; i ++ ){
        cin >> (s + 1);
        for(int j = 1;j <= wc; j ++ )
            c[i + 10][j + 10] = (s[j] == '#'); //将目标图放在中间的位置，防止合成图出界
    }
 
    for(int i = 1;i <= hc + 10; i ++ )
        for(int j = 1;j <= wc + 10; j ++ )
            for(int k = 1;k <= hc + 10; k ++ )
                for(int l = 1;l <= wc + 10; l ++ ){
                    memset(ans, 0, sizeof ans);
                    //a图覆盖 (i,j)为a图最左上端点放的位置
                    for(int p = 1;p <= ha; p ++ )
                        for(int q = 1;q <= wa; q ++ )
                            if(a[p][q]) ans[i + p - 1][j + q - 1] = 1; 
                    //b图覆盖 （k,l)为b图最左上端点放的位置
                    for(int p = 1;p <= hb; p ++ )
                        for(int q = 1;q <= wb; q ++ )
                            if(b[p][q]) ans[k + p - 1][l + q - 1] = 1;
                    
                    int f = 1;
                    for(int p = 1;p <= 30; p ++ )
                        for(int q = 1;q <= 30; q ++ )
                            if(ans[p][q] != c[p][q]) f = 0;
                    if(f){
                        cout << "Yes\n";
                        return 0;
                    }
                }
    cout << "No\n";
    return 0;
}
去括号
利用栈进行模拟
右括号也是有可能进入栈，当之前没有左括号的时候，右括号就可以入栈，比如样例4.所以还需要记录左括号数量。
我们维护一个栈，遇到左括号进栈并让计数器加一，遇到右括号，若左括号个数不为00 就弹栈直到遇到左括号，并让计数器减一。由于栈内元素总个数为nn，所以总时间复杂度为 Θ(n)Θ(n)。
相邻整数
本题是存在结论，不过可以用DP来解决。
设：
f[i][0]f[i][0]表示第i个人的选择与第一个人相同
f[i][1]f[i][1]表示第i个人的选择与第一个人不同
则：
f[i][0]=f[i−1][1];f[i][0] = f[i - 1][1];
f[i][1]=(f[i−1][0](m−1)+f[i−1][1]∗(m−2)f[i][1] = (f[i - 1][0] (m - 1) + f[i - 1][1] * (m - 2)
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=998244353;
int n,m,f[N][2];
signed main(){
	scanf("%lld%lld",&n,&m);
	f[1][0]=m;
	for(int i=2;i<=n;i++){
		f[i][0]=f[i-1][1];
		f[i][1]=(f[i-1][0]*(m-1)%mod+f[i-1][1]*(m-2)%mod)%mod;
	}
	printf("%lld",f[n][1]);
	return 0;
}
病毒感染
因为有多个起点，我们建立一个超级源点ss，它与所有已感染病毒的点连一条边权为 00的无向边。
考虑第一天，我们从超级源点 ss开始dijkstradijkstra，所有距离不超过 xx的点都会被感染病毒。然后新感染的点又会与超级源点ss连一条边权为 0的边。很显然当跑到距离大于x时我们就无需继续跑 dijkstradijkstra了。
之后第二天重复跑dijkstradijkstra，依次类推，时间复杂度是 O(dnlogm)O(dnlogm)，是无法通过的。
优化，做一遍dijkstradijkstra。
假设第一天有kk个感染源，我们只需要更新这些新感染的点邻接点点中未被感染的即可。将其加入到优先队列里。第二天就继续从这个优先队列开始dijkstradijkstra。
具体的说，假设第ii天距离感染源最近的距离为xx. dis[u]dis[u]表示uu与感染源的最短距离。
  • 若当前优先队列里距离感染源的最短距离超过xx，则说明第i天没有从感染源扩展出去, 进入第i+1i+1。
  • 否则，不断弹出能被感染的点uu，先正常松弛这些点的邻接点。记录第ii天的被感染的点。
  • 第ii天结束后，再次更新每个点到感染源的最短距离。
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
const ll inf = 1e18;
int n, m;
vector< pair<int, ll> > g[N];

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++){
		int u, v; ll w;
		scanf("%d%d%lld", &u, &v, &w);
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	
	vector<ll>dis(n + 1, inf); // dis[i]表示i与感染点的最短距离 
	vector<int>ans(n + 1, -1);
	priority_queue< pair<ll, int> > que;
	
	int k;
	scanf("%d", &k);
	while(k--){
		int u;
		scanf("%d", &u);
		dis[u] = 0;  ans[u] = 0;
		for(auto p: g[u]){
			int v = p.first;
			ll w = p.second;
			if(dis[u] + w < dis[v]){ // 将感染点的邻接点放入队列 
				dis[v] = dis[u] + w;
				que.push({-dis[v], v});
			}
		}
	}
	
	int d;
	scanf("%d", &d);
	for(int i = 1; i <= d; i++){ // 第i天,优先考虑距离感染源最近的点 
		int x;
		scanf("%d", &x); // 当前感染距离
		vector<int>tmp; //  将第i天被感染的点临时记录出来 
		while(que.size()){
			auto p = que.top();
			if(-p.first > x) break; // 若当前最小的距离 都超过感染距离， 则第i天结束，进入下一天判断
			que.pop();
			
			int u = p.second;
			if(ans[u] != -1) continue; // u点已经计算完成
			ans[u] = i;
			tmp.push_back(u);
			
			for(auto xx: g[u]){ // 松弛u的邻接点 
				int v = xx.first;
				ll w = xx.second;
				if(dis[u] + w < dis[v]){
					dis[v] = dis[u] + w;
					que.push({-dis[v], v});
				}
			}
		}
		
		//第i天结束后， 一些u点可能被感染，u的邻接点的最短距离变成了与感染源的距离，需要更新
		for(int u: tmp){
			for(auto p: g[u]){
				int v = p.first;
				ll w = p.second;
				if(dis[v] > w){ // 要么是u到v的直接距离， 要么是 v到感染源的距离 
					dis[v] = w;
					que.push({-dis[v], v});
				}
			}
		}	
	}
	
	for(int i = 1; i <= n; i++)
		printf("%d\n", ans[i]);
	
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...