GG 的 普及组 试题

本文主要是介绍GG 的 普及组 试题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.找gg

这个就是直接用字符串做就好了，注意对大小写不敏感，所以要先把所有的大写字母换成小写的（或者倒过来也行）。

时间复杂度是 \(O(n)\) 的。

代码：

#include <iostream>
#include <cstring>
using namespace std ;

int n , p[200005] , tot ;
char a[200005] ;

int main ( ) {
	cin >> ( a + 1 ) ;
	n = strlen ( a + 1 ) ;
	for ( int i = 1 ; i <= n ; ++ i )
		if ( a [ i ] >= 'A' && a [ i ] <= 'Z' )
			a [ i ] += 'a' - 'A' ;
	for ( int i = 1 ; i < n ; ++ i ) {
		if ( a [ i ] == 'g' && a [ i + 1 ] == 'g' )
			p [ ++ tot ] = i ;
	}
	cout << tot << "\n" ;
	for ( int i = 1 ; i <= tot ; ++ i )
		cout << p [ i ] << " " ;
	cout << "\n" ;
	return 0 ;
}

2.世界末日

由于每个人每个时刻都会向上走，所以我们拿一个数组用来存现在还在树上的人，然后每次让他们所在的节点调到他们的父亲上。
如果某一时刻，一个点出现了两个人，那么就删去小的那个位置，另一个值减掉小的那个值。继续放回数组就好了。
数据范围很小，时间复杂度：\(O(n^2)\)。

#include <iostream>
#include <cstring>
#include <vector>
using namespace std ;

const int N = 20005 ;
int n , m , a[N] , fa[N] ;
vector < pair < int , int > > vc ;

int calc ( int x , int y ) {
	if ( x > y ) return x - y ;
	return y - x ;
}

int main ( ) {
	cin >> n >> m ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		int ls , rs ;
		cin >> ls >> rs ;
		if ( ls ) fa [ ls ] = i ;
		if ( rs ) fa [ rs ] = i ;
	}
	for ( int i = 1 ; i <= m ; ++ i ) {
		int x , k ;
		cin >> x >> k ;
		a [ x ] = k ;
		vc .push_back ( { x , k } ) ;
	}
	while ( m > 1 ) {
		memset ( a , 0 , sizeof ( a ) ) ;
		for ( auto u : vc ) {
			int x = u .first , k = u .second ;
			if ( x != 1 )
				x = fa [ x ] ;
			if ( a [ x ] )
				a [ x ] = calc ( a [ x ] , k ) ;
			else a [ x ] = k ;
		}
		vc .clear ( ) ;
		m = 0 ;
		for ( int i = 1 ; i <= n ; ++ i )
			if ( a [ i ] != 0 )
				vc .push_back ( { i , a [ i ] } ) , ++ m ;
	}
	cout << a [ 1 ] << "\n" ;
	return 0 ;
}

3.

4.

感觉是一个标准的dp题。
首先是先对权值 \(a\) 跑一个最短路是没啥问题的，然后可以生成一个 dag 的东西。
考虑接下来怎么做，因为它有模数，所以直接做肯定是不行的。
但是可以注意到的是 \(k\) 的范围很小，所以可以直接暴力把 \(1\sim k\) 中的每个数给记录下来，然后在 dag 上做dp。
设 \(f[i][j]\) 表示在节点 i 上，是否存在一种方案满足到这个节点的路径之和取模之后的值为 \(j\)。
转移方程式就是：对一条 \(u\to v\) ，权值为 \(b_i\) 的连边。

时间复杂度为：\(O(m\log m+nk)\)。

这篇关于GG 的 普及组 试题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！