T1：GCD

title

solution

~~非常水，看一眼就知道了~~
首先我们知道每一个数都有唯一的标准整数分解，即拆成若干个质数的幂的乘积
而我们又知道质数彼此互质，(gcd()=1)
所以就可以迅速反应到，如果一个数有(ge 2)个质数因子，那么(gcd)一定等于(1)
否则(gcd)就是唯一的质数因子
这样的话，需要寻找的特殊数一定是幂级递增

欧拉筛出(n)以内的所有质数，然后进行幂级累乘，时间复杂度就是(O(nlogn))
最后加上没有被计算的数的个数即可，因为这些数每个都只会贡献(1)

~~然后直接干掉这道水题~~
在这里插入图片描述

code

#include <cstdio>
#define ll long long
#define MAXN 10000000
int a, b, cnt;
int prime[MAXN + 5];
bool vis[MAXN + 5];
ll ans[MAXN + 5];

void sieve() {
	for( int i = 2;i <= MAXN;i ++ ) {
		if( ! vis[i] )
			vis[i] = 1, prime[++ cnt] = i;
		for( int j = 1;i * prime[j] <= MAXN && j <= cnt;j ++ ) {
			vis[i * prime[j]] = 1;
			if( i % prime[j] == 0 ) break;
		}
	}
}

int main() {
	sieve();
	for( int i = 1;i <= MAXN;i ++ )
		ans[i] = 1;
	for( int i = 1;i <= cnt;i ++ ) {
		int j = 1;
		while( 1ll * j * prime[i] <= MAXN ) {
			j *= prime[i];
			ans[j] = prime[i];
		}
	}
	for( int i = 1;i <= MAXN;i ++ )
		ans[i] += ans[i - 1];
	scanf( "%d %d", &a, &b );
	printf( "%lld
", ans[b] - ans[a - 1] );
	return 0;
}

T2：包含

title

solution

这道题只要了解一点点枚举子集就能(AC)
在这里插入图片描述直接暴力一个数枚举子集
~~自测大数据跑了1.3s以为会T，但是没想到交上去能跑过诶~~

~~好了——数据加强了，终于，我被卡掉了5分~~
正解就是每次随便丢掉任何一个(1)，(O(nlogn))

#include <cstdio>
#define MAXN 1000005
int n, m;
bool vis[MAXN];

int main() {
	scanf( "%d %d", &n, &m );
	for( int i = 1, x;i <= n;i ++ ) {
		scanf( "%d", &x );
		vis[x] = 1;
	}
	for( int i = 1e6;i;i -- ) {
		if( ! vis[i] ) continue;
		for( int j = 0;j < 20;j ++ )
			if( i >> j & 1 )
				vis[i ^ ( 1 << j )] = 1;
	}
	for( int i = 1, x;i <= m;i ++ ) {
		scanf( "%d", &x );
		if( vis[x] ) printf( "yes
" );
		else printf( "no
" );
	}
	return 0;
}

code(正解code已补充在上面)

#include <cstdio>
#include <iostream>
using namespace std;
#define MAXN 100005
#define MAXM 1000000
int n, m, cnt, maxx;
int a[MAXN];
bool vis[MAXM + 5];

int main() {
	scanf( "%d %d", &n, &m );
	for( int i = 1;i <= n;i ++ ) {
		scanf( "%d", &a[i] );
		maxx = max( maxx, a[i] );
	}
	for( int i = 1;i <= n;i ++ ) {
		int x = a[i];
		if( vis[x] ) continue;
		vis[x] = 1, cnt ++;
		if( cnt == maxx ) continue;
		for( int j = x;j;j = ( ( j - 1 ) & x ) )
			if( ! vis[j] ) {
				vis[j] = 1;
				cnt ++;
				if( cnt == maxx ) break;
			}
	}
	for( int i = 1, x;i <= m;i ++ ) {
		scanf( "%d", &x );
		if( vis[x] ) printf( "yes
" );
		else printf( "no
" );
	}
	return 0;
}

T3：前缀

title

solution

大模拟！！无需多说慢慢敲，高精直接上
在这里插入图片描述

code

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
#define mod 998244353
#define MAXN 100005
vector < int > pos[30];
char s[MAXN], t[MAXN];
int pi[MAXN][2], num[MAXN];
int n, ans;

int calc( int l, int r, int siz, int len ) {
	int cnt = 0, ip;
	for( int i = l;i <= r;i ++ )
		num[i - l + 1] = t[i] ^ 48;
	for( ip = r - l + 1;! num[ip];ip -- );
	num[ip] --;
	for( int i = ip + 1;i <= r - l + 1;i ++ )
		num[i] = 9;
	int g = 0, R = 0;
	for( int i = 1;i <= r - l + 1;i ++ )
		g = R * 10 + num[i], num[++ cnt] = g / siz, R = g % siz;
	g = 0;
	for( int i = cnt;i;i -- )
		g += len * num[i], num[i] = g % 10, g /= 10;
	for( int i = 1;i <= cnt;i ++ )
		g = ( g * 10 + num[i] ) % mod;
	ans = ( ans + g ) % mod;
	return R;
}

signed main() {
	scanf( "%s", s );
	int lens = strlen( s );
	for( int i = 0;i < lens;i ++ )
		pos[s[i] ^ 96].push_back( i ), pi[i][0] = pos[s[i] ^ 96].size() - 1;
	for( int i = 0;i < lens;i ++ )
		pos[0].push_back( i ), pi[i][1] = i;
	scanf( "%lld", &n );
	while( n -- ) {
		ans = 0;
		scanf( "%s", t );
		int lent = strlen( t );
		int l = 0, r = 0, now = lens - 1, nxt, flag = 1, f;
		for( ;l < lent;l = ++ r ) {
			if( t[l] == '*' ) t[l] = 96, f = 1;
			else f = 0;
			int id = t[l] ^ 96, siz = pos[id].size();
			if( ! siz ) { flag = 0; break; }
			if( pos[id][siz - 1] <= now ) nxt = pos[id][0];
			else nxt = *upper_bound( pos[id].begin(), pos[id].end(), now );
			if( now < nxt ) ans = ( ans + nxt - now ) % mod, now = nxt;
			else ans = ( ans + lens + nxt - now ) % mod, now = nxt;
			if( l + 1 < lent && isdigit( t[l + 1] ) )
				for( ;r + 1 < lent && isdigit( t[r + 1] );r ++ );
			if( l < r ) {
				int R = calc( l + 1, r, siz, lens );
				if( R ) {
					nxt = pos[id][( pi[now][f] + R ) % siz];
					if( now < nxt ) ans = ( ans + nxt - now ) % mod, now = nxt;
					else ans = ( ans + lens + nxt - now ) % mod, now = nxt;
				}
			}
		}
		if( ! flag ) printf( "-1
" );
		else printf( "%lld
", ans );
	}
	return 0;
}

T4：移动

title

solution

~~用心出题，用脚造数据~~
~~有的代码不考虑后退错误贪心都能AC，还有暴力过去的~~
在这里插入图片描述
考虑将时间离散化，变成每个门在哪些时间段会打开，用(vector+pair)存储
大概是(n+m)个时间段

设(dp[i])表示最早到达第(i)个时间段对应的门的时间
然后用类似最短路的方法去(dp)转移，每次可以向两边转移（前提是这个门和转移到达的门都打开）
在这里插入图片描述

code

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define Pair pair < int, int >
#define inf 0x3f3f3f3f
#define MAXN 100005
struct node {
	int id, x, t;
	node() {}
	node( int Id, int X, int T ) {
		id = Id, x = X, t = T;
	}
};
priority_queue < node, vector < node >, greater < node > > q;
vector < Pair > G[MAXN], tmp;
int n, m;
int id[MAXN << 1], dp[MAXN << 1];

bool cmp( Pair x, Pair y ) {
	return x.first < y.first;
}

bool operator > ( node x, node y ) {
	return x.t > y.t;
}

void calc( node p, int x ) {
	int r = G[p.x][p.id - id[p.x]].second;
	int i = lower_bound( G[x].begin(), G[x].end(), make_pair( p.t + 1, 0 ) ) - G[x].begin() - 1;
	if( G[x][i].second >= p.t + 1 ) {
		if( dp[id[x] + i] > p.t + 1 ) {
			dp[id[x] + i] = p.t + 1;
			q.push( node( id[x] + i, x, p.t + 1 ) );
		}
	}
	i ++;
	while( i < G[x].size() && G[x][i].first <= r + 1 ) {
		if( dp[id[x] + i] > G[x][i].first ) {
			dp[id[x] + i] = G[x][i].first;
			q.push( node( id[x] + i, x, G[x][i].first ) );
		}
		i ++;
	}
}

void solve() {
	memset( dp, 0x3f, sizeof( dp ) );
	q.push( node( 0, 0, 0 ) );
	dp[0] = 0;
	while( ! q.empty() ) {
		node now = q.top(); q.pop();
		if( now.t > dp[now.id] ) continue;
		if( now.x > 0 ) calc( now, now.x - 1 );
		if( now.x <= n ) calc( now, now.x + 1 );
	}
}

int main() {
	scanf( "%d %d", &n, &m );
	for( int i = 1, a, b, c;i <= m;i ++ ) {
		scanf( "%d %d %d", &a, &b, &c );
		G[a].push_back( make_pair( b, c ) );
	}
	G[0].push_back( make_pair( 0, inf ) );
	G[n + 1].push_back( make_pair( 0, inf ) );
	id[1] = 1;
	for( int i = 1;i <= n;i ++ ) {
		tmp.clear();
		sort( G[i].begin(), G[i].end(), cmp );
		int r = -1;
		for( int j = 0;j < G[i].size();j ++ ) {
			if( G[i][j].first > r + 1 ) tmp.push_back( make_pair( r + 1, G[i][j].first - 1 ) );
			r = max( r, G[i][j].second );
		}
		tmp.push_back( make_pair( r + 1, inf ) );
		G[i] = tmp;
		id[i + 1] = id[i] + G[i].size();
	}
	solve();
	printf( "%d
", dp[id[n + 1]] );
	return 0;
}