LibreOJ NOIP Round #1 Day 1

Day 1

T1. DNA 序列

水题，最直观的解法是hash，发现k<=10后发现转化为二进制压位也行

定位：noip d1t1，送分题

#include <bits/stdc++.h>
using namespace std;
const int N = 5000000 + 5;
char s[N];
int a[N<<1], b[1<<20], K, n, now, ans;
int main(){
	scanf( "%s", s + 1 ); n = strlen(s + 1);
	scanf( "%d", &K );
	for( int i = 1; i <= n; i++ ){
		if( s[i] == 'A' ) a[i*2-1] = 0, a[i*2] = 0;
		if( s[i] == 'G' ) a[i*2-1] = 0, a[i*2] = 1;
		if( s[i] == 'C' ) a[i*2-1] = 1, a[i*2] = 0;
		if( s[i] == 'T' ) a[i*2-1] = 1, a[i*2] = 1;
	}
	for( int i = 1; i <= K*2; i++ ) now <<= 1, now += a[i];
	for( int i = K * 2; i <= n * 2; i += 2 ){
		b[now]++;
		if( b[now] > ans ) ans = b[now];
		if( i == n * 2 ) break;
		now <<= 1; now += a[i + 1];
		now %= (1<<(K*2));
		now <<= 1; now += a[i + 2];
		now %= (1<<(K*2));
	}
	printf( "%d\n", ans );
	return 0;
}

T2. 递推数列

这道题具有一些迷惑性，我们看到k>0

首先考虑ai,ai-1同号，可以推出ai+1也同号并且绝对值更大

也就是在这之后ai具有单调性

那我们只需要求出没有单调性之前的所有数就行了（有单调性之后还是要算出更大的）

定义：不按常理的题

题解中的证明：

设 $b_i=|a_i|$ ，由正负交错有 $∀i∈[2,M),bi=−kbi−1+bi−2\forall i\in[2,M), b_i=-k b_{i-1}+b_{i-2}$ ，移项得 $b_{i-2}=k b_{i-1}+b_i$ 。

那么 $bi−2=kbi−1+bi≥(k+1)bib_{i-2}=k b_{i-1}+b_i\ge (k+1)b_i$ ，可得 $M≤2logk+1a0M\le 2\log_{k+1} a_0$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300000 + 5;
ll a[105]; int m, n, s[N], K, minsi, maxsi, t;
int main(){
	scanf( "%d", &m ); for( int i = 1; i <= m; i++ ) scanf( "%d", &s[i] );
	scanf( "%d", &n );
	while( n-- ){
		scanf( "%lld%lld%d", &a[0], &a[1], &K ); minsi = maxsi = s[1];
		if( !a[0] && !a[1] ){ printf( "%d %d\n", s[1], s[1] ); continue; }
		for( t = 2; t <= 100 && abs( a[t] = a[t - 1] * K + a[t - 2] ) <= 1e14; t++ ); t--;
		for( int i = 1; i <= m && s[i] <= t; i++ ){
			minsi = ( a[s[i]] < a[minsi] ) ? s[i] : minsi;
			maxsi = ( a[s[i]] > a[maxsi] ) ? s[i] : maxsi;
		}
		if( s[m] > 100 ) a[t] < 0 ? minsi = s[m] : maxsi = s[m];
		printf( "%d %d\n", maxsi, minsi );
	}
	return 0;
}

T3. 旅游路线

这道题看了题解 ~~（chao了代码）~~后觉得挺简单的，但是考试时做得出来？

这可能就相当于我对去年noip t3 t6的定义吧（虽然那两道确实简单啊）

w[i][j][k]：从i到j经过不超过2^k长度的最长距离

dis[i][j]：从i出发（先在i加油到j的最大路程（可能到j加油也可能不走））

dp[i][j]：从i出发带j元钱的最大路程

从w数组转移到dis数组的时候要注意要用一个f数组存中间点

转移方程：

w[i][j][k] = w[i][l][k - 1] + w[l][j][k - 1]

f[j] = g[l] + w[l][j][k]

dp[i][k] = max{ dp[j][k - p[i]] + dis[i][j] }

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 2e15;
int n, m, C, T, last[105], cnt, p[105], c[105]; ll w[105][105][20], g[105], f[105], dis[105][105], dp[105][10005];/*price youliang*/
/*Ã¿ÐÐ°üº¬Èý¸öÕýÕûÊý si,qi,di,ÃèÊöÒ»´ÎÂÃÓÎ¼Æ»®£¬ÂÃÓÎµÄÆðµãÎª±àºÅÎª siµÄ¾°µã£¬³ö·¢Ê±´øÁË qiÔªÇ®£¬Ä¿±êÂ·³ÌÎª di.*/
int main(){
	scanf( "%d%d%d%d", &n, &m, &C, &T );
	for( int i = 1; i <= n; i++ ) scanf( "%d%d", &p[i], &c[i] ), c[i] = min( c[i], C );
	memset( w, 0xc2, sizeof(w) ); for( int i = 1; i <= n; i++ ) w[i][i][0] = 0;
	for( int i = 1, u, v, ww; i <= m; i++ ) scanf( "%d%d%d", &u, &v, &ww ), w[u][v][0] = max( w[u][v][0], (ll)ww );
	for( int k = 1; k <= 18; k++ )
		for( int l = 1; l <= n; l++ )
			for( int i = 1; i <= n; i++ )
				for( int j = 1; j <= n; j++ )
					w[i][j][k] = max( w[i][j][k], w[i][l][k - 1] + w[l][j][k - 1] );
	for( int i = 1; i <= n; i++ ){
		for( int j = 1; j <= n; j++ ) g[j] = ( i == j ? 0 : -inf ), f[j] = -inf;
		for( int k = 18; k >= 0; k-- )
			if( c[i] & (1<<k) ){
				for( int j = 1; j <= n; j++ )
					for( int l = 1; l <= n; l++ )
						f[j] = max( f[j], g[l] + w[l][j][k] );
				for( int j = 1; j <= n; j++ ) g[j] = f[j];
			}
		for( int j = 1; j <= n; j++ ) dis[i][j] = g[j];
	}
	int lim = n * n;
	for( int k = 0; k <= lim; k++ )
		for( int i = 1; i <= n; i++ )
			if( k >= p[i] )
				for( int j = 1; j <= n; j++ )
					dp[i][k] = max( dp[i][k], dp[j][k - p[i]] + dis[i][j] );
	while( T-- ){
		int S, Q, D;
		scanf( "%d%d%d", &S, &Q, &D );
		int ans = Q + 1;
		for( int i = 0; i <= Q; i++ )
			if( dp[S][i] >= D ){ ans = i; break; }
		printf( "%d\n", Q - ans );
	}
	return 0;
}

Day 2

T1. 游戏

我是不是太弱了，t1想了那么久都没有想出来。

完全图重有一个1个环的 Example：1-2-3-1

我们猜测一定可以贪心地拆成完全图

试了所有数据后发现有解，所以贪心（逗逼解法）

定义：noip d2t1 但是感觉太坑了，与数列递推一样坑

#include <bits/stdc++.h>
using namespace std;
int f( int xx ){ return xx * (xx - 1) * (xx - 2) / 6; }
int x, n, mp[505][505];
int main(){
	scanf( "%d", &x );
	for( int i = 500; i >= 3; i-- ){
		if( x >= f(i) ){
			x -= f(i);
			for( int j = n + 1; j <= n + i; j++ )
				for( int k = j + 1; k <= n + i; k++ )
					mp[j][k] = 1;
			n += i;
			i++;
		}
	}
	printf( "%d\n", n );
	for( int i = 1; i <= n; i++ ){
			for( int j = i + 1; j <= n; j++ )
				printf( "%d ", mp[i][j] );
		puts("");
	}
	return 0;
}

T2. 七曜圣贤

我觉得这道题比上一道题好想的多好吗

首先用一个队列q维护飞出去的红茶是个人都想得到，维护一个数据结构，存到是这个队列里面的元素

用一个bool数组存一样红茶买没有买过，用一个变量now表示1到now都被买过了（只会增长）

购买操作：改一个bool，跳now

飞出去操作：入队尾，入这个数据结构

捡回来操作：队首出

显然这时答案就是min( now, 队列里面所有点编号的最小值 )

没错，这个数据结构就是单调队列

定义：类似去年蚯蚓，但是更简单

#include <bits/stdc++.h>
using namespace std;
namespace IO{
	int c;
	unsigned int seed;
	unsigned int randnum(){
		seed ^= seed<<13;
		seed ^= seed>>17;
		seed ^= seed<<5;
		return seed;
	}

	inline int read( int &x ){ scanf( "%d", &x ); return x; }
	inline void init_case( int &m, int &a, int &b, int &d, int p[] ){
		scanf( "%d%u%d%d%d%d", &m, &seed, &a, &b, &c, &d );
		for( int i = 1; i <= m; i++ ){
			if( randnum() % c == 0 ) p[i] = -1;
			else p[i] = randnum() % b;
		}
	}
	inline void update_ans( unsigned int &ans_sum, unsigned int cur_ans, int no ){
		const static unsigned int mod = 998244353;
		ans_sum ^= ( 1LL * no * (no + 7) % mod * cur_ans % mod );
	}
}
using IO::read;
using IO::init_case;
using IO::update_ans;
bool incar[2000005], fly[2000005];
unsigned int q1[2000005], t1, h1, q2[2000005], t2, h2;
/*
now:当前最大且已经被买过
q1:按扔出时间递增 
q2:扔出时间递增，编号递增（ 1 3 5 2 8 4 -> 1 2 4 ） 
*/
/*
pi==-1 最早飞出的回收
否则，如果没有买过就买一个
否则，如果在车上，则飞出
否则，最早飞出的回收，不存在则忽略 
*/
int main(){
	static int p[2000005];
	int T; read( T );
	int m, a, b, d;
	while( T-- ){
		unsigned int ans_sum = 0, cur_ans = 0, now = 0;
		t1 = t2 = 0; h1 = h2 = 1;
		init_case( m, a, b, d, p );
		memset( q1, 0, sizeof(q1) );
		memset( q2, 0, sizeof(q2) );
		memset( fly, 0, sizeof(fly) );
		memset( incar, 0, sizeof(incar) );
		for( int i = 1; i <= a + 1; i++ ) incar[i] = 1;
		while( incar[now + 1] ) now++;
		for( int i = 1; i <= m; i++ ){
			p[i]++;
			if( p[i] == 0 ){
				if( d ) continue;
				if( h1 > t1 ) continue;
				fly[q1[h1]] = 0;
				if( q1[h1] == q2[h2] ) h1++, h2++;
				else h1++;
			}else if( !incar[p[i]] ){
				incar[p[i]] = 1;
				while( incar[now + 1] ) now++;
			}else if( incar[p[i]] && !fly[p[i]] ){
				if( d ) continue;
				fly[p[i]] = 1;
				q1[++t1] = p[i];
				while( t2 >= h2 && p[i] < q2[t2] ) t2--;
				q2[++t2] = p[i];
			}else {
				if( d ) continue;
				if( h1 > t1 ) continue;
				fly[q1[h1]] = 0;
				if( q1[h1] == q2[h2] ) h1++, h2++;
				else h1++;
			}
			cur_ans = now;
			if( h2 <= t2 ) cur_ans = min( cur_ans, q2[h2] - 1 );
			update_ans( ans_sum, cur_ans, i );
        }
		printf( "%u\n", ans_sum );
	}
	return 0;
}
/*
10
3000 951860881 2869 3500 5 0
2000 220202994 1745 3400 15 1
3000 930087169 1624 3500 50 0
3000 881772733 2368 3500 15 0
3000 466277267 1122 3500 54 0
2900 742047150 1965 2500 25 0
3000 531934116 783 2500 10000000 1
3000 175160586 2783 2500 5 0
2333 229062998 2594 3500 55 0
3000 555447828 2489 3500 555 0
*/
 子任务 #1

T3. 序列划分

定义：NOI d1t2

做不来

秒客网

LibreOJ NOIP Round #1 —— 蒟蒻总结&部分题解