首页 > 其他分享 >考试心得1

考试心得1

时间：2024-08-20 14:26:09浏览次数：3  
标签：int ll cin long maxn 考试 心得 dp

当然这篇博客写的比较难评啊（指没有折叠代码，只是从洛谷搬过来，将就着看吧。。。

\(\mathtt{2024/2/18}\)

由于作者不会map而导致T2挂90分，特此纪念

T1 家庭作业

最简单的一道题。可以考虑分解质因数，但考场上我想到了却并没有打出来（），所以选择了另一个方法。

考虑将 \(b\) 数组和 \(a\) 数组的每一个数求最大公因数，然后再将 \(a[j]\) 和 \(b[i]\) 共同除以这个公因数（因为会有重复计算），最后将这些公因数都相乘，记得取模。

不懂得看代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, m, a[1005], b[1005], t, ans=1, tmp, num=1;
ll gcd(ll a,ll b)
{
    if(a%b==0)
    {
        return b;
    }
    return gcd(b, a%b);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);	
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>b[i];
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			num=gcd(a[j], b[i]);
			ans*=num;
			a[j]/=num;
			b[i]/=num;
		}
		ans%=1000000000;
	}
	cout<<ans%1000000000;
	return 0;
}

T2 距离之和

/(#>д<)ﾉ我不会用map啊

看到此题，可能第一眼想到暴力，但时间复杂度是\(O(nm)\)的，肯定过不了（但也有50啊呜呜呜），
然后考虑\(O(m)\)的做法。

在输入的时候，我们就可以先预处理出上、下、左、右四个方向的固定点（以\(x,y\)轴位界限），再定义两个变量存储\(xy\)上的固定点，再存储下每一行、每一列的固定点个数（注意用\(map\)存储，因为有可能是负数），然后算好初始\(sum\)值。还要再定义两个变量，表示\(x,y\)轴（每走一步界限都在变化）。

接下来开始机器人移动。比如机器人向上走，那么\(sum\)值就要加上下面和\(x\)轴的固定点个数，减去上面的固定点个数。\(x\)轴就要往上移一格，那么原先\(x\)轴上的固定点就属于下面的了，等等。其他变量要更新。其他方向同理。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, m, x, y,  sum, dy, dx, l, r, u, d, yz, xz; 
string s;
map<int,int> a, b;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);	
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y;
		if(x<0)
			l++;
		else if(x>0)
			r++;
		else
			dy++;//竖 
		if(y<0)
			d++;
		else if(y>0)
			u++;
		else
			dx++;//横 
		a[x]++;
		b[y]++;
		sum+=(abs(x)+abs(y));
	}
	cin>>s;
	for(int i=0;i<m;i++)
	{
		if(s[i]=='S')
		{
			sum+=d-u+dx;
			yz++;
			d+=dx;
			u-=b[yz];
			dx=b[yz];
		}
		else if(s[i]=='J')
		{
			sum+=u-d+dx;
			yz--;
			u+=dx;
			d-=b[yz];
			dx=b[yz];
		}
		else if(s[i]=='I')
		{
			sum+=l-r+dy;
			xz++;
			l+=dy;
			r-=a[xz];
			dy=a[xz];
		}
		else
		{
			sum+=r-l+dy;
			xz--;
			r+=dy;
			l-=a[xz];
			dy=a[xz];
		}
		cout<<sum<<endl;
		//sum=0;
	}
	return 0;
}

T3

正在写

T4 太空飞船

容斥原理。

题解（讲得很清楚吧）

简单来讲，就是利用容斥原理推出这个式子，最后统计答案。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, m, a[100005], num[100005], tmp, cnt;
ll ans, c[10005];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;		
	for(int i=4;i<=1e4;i++)
	{
		c[i]=1ll*i*(i-1)*(i-2)*(i-3)/24;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		num[a[i]]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=2;j*j<=a[i];j++)
		{
			if(a[i]%j==0)
			{
				num[j]++;	
				if(j*j!=a[i])
					num[a[i]/j]++;
			}
		}
	}
	ans=c[n];
	//cout<<ans<<endl;
	for(int i=1;i<=1e4;i++)
	{
		bool f=0;
        for(int j=2;j*j<=i;j++)
        {
        	if(i%j==0&&i/j%j==0)
      	    {
            	f=1;
            	break;
         	}
		}  
        if(f==1) 
			continue;
		cnt=0;
		int t=i;
		for(int j=2;j*j<=t;j++)
		{
			if(t%j==0)
			{
				cnt++;
				while(t%j==0)
					t/=j;
			}
		}
		if(t!=1)
			cnt++;
		if(cnt%2==1)
		{
			ans-=c[num[i]];
		}
		else
		{
			ans+=c[num[i]];
		}
	}
	cout<<ans;
	return 0;
}

\(\mathtt{2024/2/19}\)

T1 素数

暴力枚举32767以内的质数，然后暴力计算，值相同方案数就++。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a, tot, ans, pri[1901]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,4001,4003,4007,4013,4019,4021,4027,4049,4051,4057,4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,4153,4157,4159,4177,4201,4211,4217,4219,4229,4231,4241,4243,4253,4259,4261,4271,4273,4283,4289,4297,4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,4421,4423,4441,4447,4451,4457,4463,4481,4483,4493,4507,4513,4517,4519,4523,4547,4549,4561,4567,4583,4591,4597,4603,4621,4637,4639,4643,4649,4651,4657,4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,4759,4783,4787,4789,4793,4799,4801,4813,4817,4831,4861,4871,4877,4889,4903,4909,4919,4931,4933,4937,4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,5009,5011,5021,5023,5039,5051,5059,5077,5081,5087,5099,5101,5107,5113,5119,5147,5153,5167,5171,5179,5189,5197,5209,5227,5231,5233,5237,5261,5273,5279,5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,5393,5399,5407,5413,5417,5419,5431,5437,5441,5443,5449,5471,5477,5479,5483,5501,5503,5507,5519,5521,5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,5641,5647,5651,5653,5657,5659,5669,5683,5689,5693,5701,5711,5717,5737,5741,5743,5749,5779,5783,5791,5801,5807,5813,5821,5827,5839,5843,5849,5851,5857,5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,5953,5981,5987,6007,6011,6029,6037,6043,6047,6053,6067,6073,6079,6089,6091,6101,6113,6121,6131,6133,6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,6229,6247,6257,6263,6269,6271,6277,6287,6299,6301,6311,6317,6323,6329,6337,6343,6353,6359,6361,6367,6373,6379,6389,6397,6421,6427,6449,6451,6469,6473,6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,6577,6581,6599,6607,6619,6637,6653,6659,6661,6673,6679,6689,6691,6701,6703,6709,6719,6733,6737,6761,6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,6841,6857,6863,6869,6871,6883,6899,6907,6911,6917,6947,6949,6959,6961,6967,6971,6977,6983,6991,6997,7001,7013,7019,7027,7039,7043,7057,7069,7079,7103,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,7211,7213,7219,7229,7237,7243,7247,7253,7283,7297,7307,7309,7321,7331,7333,7349,7351,7369,7393,7411,7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,7507,7517,7523,7529,7537,7541,7547,7549,7559,7561,7573,7577,7583,7589,7591,7603,7607,7621,7639,7643,7649,7669,7673,7681,7687,7691,7699,7703,7717,7723,7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,7841,7853,7867,7873,7877,7879,7883,7901,7907,7919,7927,7933,7937,7949,7951,7963,7993,8009,8011,8017,8039,8053,8059,8069,8081,8087,8089,8093,8101,8111,8117,8123,8147,8161,8167,8171,8179,8191,8209,8219,8221,8231,8233,8237,8243,8263,8269,8273,8287,8291,8293,8297,8311,8317,8329,8353,8363,8369,8377,8387,8389,8419,8423,8429,8431,8443,8447,8461,8467,8501,8513,8521,8527,8537,8539,8543,8563,8573,8581,8597,8599,8609,8623,8627,8629,8641,8647,8663,8669,8677,8681,8689,8693,8699,8707,8713,8719,8731,8737,8741,8747,8753,8761,8779,8783,8803,8807,8819,8821,8831,8837,8839,8849,8861,8863,8867,8887,8893,8923,8929,8933,8941,8951,8963,8969,8971,8999,9001,9007,9011,9013,9029,9041,9043,9049,9059,9067,9091,9103,9109,9127,9133,9137,9151,9157,9161,9173,9181,9187,9199,9203,9209,9221,9227,9239,9241,9257,9277,9281,9283,9293,9311,9319,9323,9337,9341,9343,9349,9371,9377,9391,9397,9403,9413,9419,9421,9431,9433,9437,9439,9461,9463,9467,9473,9479,9491,9497,9511,9521,9533,9539,9547,9551,9587,9601,9613,9619,9623,9629,9631,9643,9649,9661,9677,9679,9689,9697,9719,9721,9733,9739,9743,9749,9767,9769,9781,9787,9791,9803,9811,9817,9829,9833,9839,9851,9857,9859,9871,9883,9887,9901,9907,9923,9929,9931,9941,9949,9967,9973,10007,10009,10037,10039,10061,10067,10069,10079,10091,10093,10099,10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193,10211,10223,10243,10247,10253,10259,10267,10271,10273,10289,10301,10303,10313,10321,10331,10333,10337,10343,10357,10369,10391,10399,10427,10429,10433,10453,10457,10459,10463,10477,10487,10499,10501,10513,10529,10531,10559,10567,10589,10597,10601,10607,10613,10627,10631,10639,10651,10657,10663,10667,10687,10691,10709,10711,10723,10729,10733,10739,10753,10771,10781,10789,10799,10831,10837,10847,10853,10859,10861,10867,10883,10889,10891,10903,10909,10937,10939,10949,10957,10973,10979,10987,10993,11003,11027,11047,11057,11059,11069,11071,11083,11087,11093,11113,11117,11119,11131,11149,11159,11161,11171,11173,11177,11197,11213,11239,11243,11251,11257,11261,11273,11279,11287,11299,11311,11317,11321,11329,11351,11353,11369,11383,11393,11399,11411,11423,11437,11443,11447,11467,11471,11483,11489,11491,11497,11503,11519,11527,11549,11551,11579,11587,11593,11597,11617,11621,11633,11657,11677,11681,11689,11699,11701,11717,11719,11731,11743,11777,11779,11783,11789,11801,11807,11813,11821,11827,11831,11833,11839,11863,11867,11887,11897,11903,11909,11923,11927,11933,11939,11941,11953,11959,11969,11971,11981,11987,12007,12011,12037,12041,12043,12049,12071,12073,12097,12101,12107,12109,12113,12119,12143,12149,12157,12161,12163,12197,12203,12211,12227,12239,12241,12251,12253,12263,12269,12277,12281,12289,12301,12323,12329,12343,12347,12373,12377,12379,12391,12401,12409,12413,12421,12433,12437,12451,12457,12473,12479,12487,12491,12497,12503,12511,12517,12527,12539,12541,12547,12553,12569,12577,12583,12589,12601,12611,12613,12619,12637,12641,12647,12653,12659,12671,12689,12697,12703,12713,12721,12739,12743,12757,12763,12781,12791,12799,12809,12821,12823,12829,12841,12853,12889,12893,12899,12907,12911,12917,12919,12923,12941,12953,12959,12967,12973,12979,12983,13001,13003,13007,13009,13033,13037,13043,13049,13063,13093,13099,13103,13109,13121,13127,13147,13151,13159,13163,13171,13177,13183,13187,13217,13219,13229,13241,13249,13259,13267,13291,13297,13309,13313,13327,13331,13337,13339,13367,13381,13397,13399,13411,13417,13421,13441,13451,13457,13463,13469,13477,13487,13499,13513,13523,13537,13553,13567,13577,13591,13597,13613,13619,13627,13633,13649,13669,13679,13681,13687,13691,13693,13697,13709,13711,13721,13723,13729,13751,13757,13759,13763,13781,13789,13799,13807,13829,13831,13841,13859,13873,13877,13879,13883,13901,13903,13907,13913,13921,13931,13933,13963,13967,13997,13999,14009,14011,14029,14033,14051,14057,14071,14081,14083,14087,14107,14143,14149,14153,14159,14173,14177,14197,14207,14221,14243,14249,14251,14281,14293,14303,14321,14323,14327,14341,14347,14369,14387,14389,14401,14407,14411,14419,14423,14431,14437,14447,14449,14461,14479,14489,14503,14519,14533,14537,14543,14549,14551,14557,14561,14563,14591,14593,14621,14627,14629,14633,14639,14653,14657,14669,14683,14699,14713,14717,14723,14731,14737,14741,14747,14753,14759,14767,14771,14779,14783,14797,14813,14821,14827,14831,14843,14851,14867,14869,14879,14887,14891,14897,14923,14929,14939,14947,14951,14957,14969,14983,15013,15017,15031,15053,15061,15073,15077,15083,15091,15101,15107,15121,15131,15137,15139,15149,15161,15173,15187,15193,15199,15217,15227,15233,15241,15259,15263,15269,15271,15277,15287,15289,15299,15307,15313,15319,15329,15331,15349,15359,15361,15373,15377,15383,15391,15401,15413,15427,15439,15443,15451,15461,15467,15473,15493,15497,15511,15527,15541,15551,15559,15569,15581,15583,15601,15607,15619,15629,15641,15643,15647,15649,15661,15667,15671,15679,15683,15727,15731,15733,15737,15739,15749,15761,15767,15773,15787,15791,15797,15803,15809,15817,15823,15859,15877,15881,15887,15889,15901,15907,15913,15919,15923,15937,15959,15971,15973,15991,16001,16007,16033,16057,16061,16063,16067,16069,16073,16087,16091,16097,16103,16111,16127,16139,16141,16183,16187,16189,16193,16217,16223,16229,16231,16249,16253,16267,16273,16301,16319,16333,16339,16349,16361,16363,16369,16381};
int main()
{
	while(cin>>a&&a)
	{
		int cnt=0;
		for(int i=1;i<=1900;i++)
		{
			int t=pri[i];
			if(a==pri[i])
			{
				cnt++;
				continue;
			}
			for(int j=i+1;j<=1900;j++)
			{
				t+=pri[j];
				if(t==a)
				{
					cnt++;
					break;
				}
				else if(t>a)
				{
					break;
				}
			}
		}	
		cout<<cnt<<endl;
	}
	return 0;
}

T2 晨练

dp好吧。\(dp[i][j]\)表示第\(i\)分钟，疲劳值为\(j\)的情况下最远能跑多少。初始化\(dp[1][0]=0,dp[1][1]=d[1]\),分情况讨论状态转移方程。

#include <stdio.h>
#include <iostream>
using namespace std;
int n,m,a[10001],dp[10505][1001],s;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	dp[1][0]=0;
	dp[1][1]=a[1];
	for(int i=1;i<=n;i++)
	{
		dp[i][0]=max(dp[i][0],dp[i-1][0]);
		for(int j=1;j<=min(i,m);j++) 
		{
			dp[i][j]=max(dp[i][j],dp[i-1][j-1]+a[i]);
			dp[i+j][0]=max(dp[i][j],dp[i+j][0]);
		}
	}
	cout<<dp[n][0]<<endl;;
	return 0;
}

T3 奇怪的桌子

又一道dp。对于第i列，可以发现所有\(i\)%\(n\)为相同值的，放的个数一定是相同的。
\(dp[i][j]\)表示到第\(i\)列，已放\(j\)个的方案数。

$ dp[i][j]+=f[i−1][j−p]∗C(n,p) ^{
(m/n+(i<=n/m））}$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
ll n, k;
ll m, f[105],g[105],dp[105][11025], t[105][105];
ll fpow(ll a,ll b) 
{
    ll ans=1;
    while(b)
    {
        if(b&1)
        {
            ans*=a;
            ans%=mod;
        }
        b>>=1;
        a*=a;a%=mod;
    }
    return ans;
}
void init()
{
    f[0]=g[0]=1;
    for(int i=1;i<=100;i++)
    {
        f[i]=f[i-1]*i%mod;
        g[i]=g[i-1]*fpow(i, mod-2)%mod;
    }
}
ll C(ll n, ll m)
{
	if(n==0||m==0||n<m)
	{
		return 1;
	} 
    return f[n]*g[m]%mod*g[n-m]%mod;
}
int main()
{
    cin>>n>>m>>k;
    init();
    for(int i=0;i<=n;i++)
	{
		t[0][i]=fpow(C(n,i),m/n);
		t[1][i]=t[0][i]*C(n,i)%mod;
	}
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
	{
	    for(int j=max(0*1ll,k-n*(n-i));j<=min(k,n*i);j++)
		{
			for(int p=0;p<=min(n,j*1ll);p++)
			{
				if(i<=(m%n))
				{
					dp[i][j]=(dp[i][j]+dp[i-1][j-p]*t[1][p]%mod)%mod;
				}
				else
				{
					dp[i][j]=(dp[i][j]+dp[i-1][j-p]*t[0][p]%mod)%mod;	
				}	
			}		
		}
    }
    cout<<dp[n][k];
    return 0;
}

T4 学校

跑一遍最短路，保留从\(s\)到\(t\)上所有的最短路建图。判断一条边是否是割边（割边是指将某个图中某个顶点和与其连接的边（桥）割掉，使得该图被分为两部分，不相连的情况。如果去掉一个点以及与它连接的边，该点原来所在的图被分成两部分，则称该点为割点；如果去掉一条边，该边原来所在的图被分成两部分，则称该点为割边）即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+10;
int n, m, a, x, y, z, vis[maxn], s, t, dis[maxn], low[maxn], dfn[maxn], idx, k;
int head[maxn], edgenum, h[maxn];
bool bri[maxn];
struct edge{
   int next;
   int to;
   int w;
   int id;
}edge[maxn<<1], e[maxn<<1];
void add(int from,int to,int w,int id)
{
   edge[++edgenum].next=head[from];
   edge[edgenum].to=to;
   edge[edgenum].w=w;
   edge[edgenum].id=id;
   head[from]=edgenum;
}
void add1(int from,int to,int w,int id)
{
   e[++edgenum].next=h[from];
   e[edgenum].to=to;
   e[edgenum].w=w;
   e[edgenum].id=id;
   h[from]=edgenum;
}
/*void dijkstra(int u)
{
   for(int i=1;i<=n;i++)   
       dis[i]=1e9;
   dis[u]=0;
   for(int i=1;i<n;i++)
   {
       int mark=-1, mindis=1e9; 
   	for(int j=1;j<=n;j++)
   	{
   		if(!vis[j]&&dis[j]<mindis)       
       	{
       	    mindis=dis[j];    
       	    mark=j;
       	}
   	}      
       vis[mark]=1;   
   	for(int i=head[mark];i;i=edge[i].next)
   	{
   	    int v=edge[i].to;
   	    if(!vis[v])       
   	        dis[v]=min(dis[v], dis[mark]+edge[mark].w);             
   	}
   }
   
}*/
priority_queue<pair<int,int> >q;
void dijkstra(int s)
{
   q.push(make_pair(0,s));
   for(int i=1;i<=n;i++) dis[i]=2e9;
   dis[s]=0;
   while(!q.empty())
   {
       int w=q.top().first*(-1),u=q.top().second;
       q.pop();
       if(w!=dis[u]) continue;
       for(int i=head[u];i;i=edge[i].next)
       {
           int v=edge[i].to;
           if(dis[u]+edge[i].w<dis[v])
           {
               dis[v]=dis[u]+edge[i].w;
               q.push(make_pair(-dis[v],v));
           }
       }
   }
}
void dfs(int u)
{
   if(u==s||vis[u])
   {
   	return ;
   }
   vis[u]=1;
   //cout<<1<<endl;
   for(int i=head[u];i;i=edge[i].next)
   {
   	int v=edge[i].to;
   	if(edge[i].w+dis[v]==dis[u])
   	{
   		add1(u, v, edge[i].w, edge[i].id);
   		add1(v, u, edge[i].w, edge[i].id);
   		dfs(v);
   	}
   }
} 
void tarjan(int u,int edg)
{
   dfn[u]=low[u]=++idx;
   for(int i=h[u];i;i=e[i].next)
   {
   	int v=e[i].to;
   	if(!dfn[v])
   	{
   		tarjan(v, i);
   		low[u]=min(low[u], low[v]);
   		if(dfn[u]<low[v])
   		{
   			bri[e[i].id]=1;
   		}
   	}
   	else if(i!=(edg^1))
   	{
   		low[u]=min(low[u],dfn[v]);
   	}
   }
}
int main()
{
   cin>>n>>m>>s>>t;
   for(int i=1;i<=m;i++)
   {
   	cin>>x>>y>>z;
   	add(x, y, z, i);
   	add(y, x, z, i);
   } 
   dijkstra(s);
   edgenum=1;
   dfs(t);
   tarjan(s, 0);
   cin>>k;
   for(int i=1;i<=k;i++)
   {
   	cin>>a;	
   	if(!bri[a])
   	{
   		cout<<"Yes"<<endl;
   	}
   	else
   	{
   		cout<<"No"<<endl;
   	}
   } 
   return 0;
}

\(\mathtt{2024/2/21}\)

难

T1 排序

太简单了没必要讲。找到规律即可：将数列分成两半，前\(2n\)个一大一小配对，后\(2n\)个相邻两两配对。

但是，注意爆零（数组要开4倍，要开 long long）

#include<bits/stdc++.h>
using namespace std;
long long n, a[(100005)<<2], ans;
int main()
{
	cin>>n;
	for(int i=1;i<=4*n;i++)
	{
		cin>>a[i];
	}
	sort(a+1, a+4*n+1);
	for(int i=2*n+1,j=1;i<=4*n,j<=n;i=i+2,j++)
	{
		ans+=a[i]*a[i+1]; 
		ans-=a[j]*a[2*n-j+1];
	}
	cout<<ans;
	return 0;
}

T2 牛吃草

看到这个题目有没有想到小奥？

正解：二分答案+单调队列优化dp
老师的题解

第二个式子不要看。
观察第一个\(dp\)式子，\(f[i-1]\)是固定的，所以我们要维护的是\(f[j]+(i-j)\)中的\(f[j]-j\)的最大值。

#include<bits/stdc++.h>
using namespace std;
int n, m, w[500005], dp[500005], p, q, ans, s, t;
bool check(int size)
{
	deque<int> q;
	memset(dp, 0, sizeof(dp));
	for(int i=1;i<=n;i++)
	{
		int tmp=i-size;
		dp[i]=dp[i-1];
		if(tmp>=0)
		{
			while(!q.empty()&&dp[q.back()]-q.back()<=dp[tmp]-tmp)
    		{
    		    q.pop_back();
    		} 
    		q.push_back(tmp);
		}
    	while(!q.empty()&&q.front()<i-w[i])
   		{
   		    q.pop_front();
   		} 
   		if(w[i]>=size)
   		{
   			if(!q.empty())
   				dp[i]=max(dp[q.front()]+i-q.front(), dp[i-1]);	
		}	
	}	
	if(dp[n]>=t)
		return 1;
	return 0;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i];
	}
	cin>>s;
	t=ceil(n*s*1.0/100);
	int l=1, r=n;
	//cout<<t<<endl;
	while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
        {
            ans=mid;
            l=mid+1;
        }
        else
        {
            r=mid-1;
        }
    }
	cout<<ans;
	return 0;
}

全局定义后的变量不要在局部再次定义。

T3 树上的宝藏

完全不会。


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e6+5, mod=998244353;
ll f[MAXN][2], g[MAXN][2], s, ans, vis[MAXN], u[MAXN], v[MAXN];
int dep[MAXN];
ll fpow(ll a, ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
int n, head[MAXN], edgenum;
struct edge{
    int next;
    int to;
    int w;
};
edge edge[MAXN];
void add(int from,int to)
{
    edge[++edgenum].next=head[from];
    edge[edgenum].to=to;
    head[from]=edgenum;
}
void dfsf(int x,int fa)
{
	f[x][0]=f[x][1]=1;
	dep[x]=dep[fa]+1;
	for(int i=head[x];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa)	continue;
		dfsf(v, x);
		f[x][0]=f[x][0]*(f[v][0]+f[v][1])%mod;
		f[x][1]=f[x][1]*f[v][0]%mod;
		
	}
}
void dfsg(int u,int fa)
{
    ll s=g[u][0],t=g[u][1];
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        s=s*(f[v][0]+f[v][1])%mod;
        t=t*f[v][0]%mod;
    }
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        ll s1=s*fpow((f[v][0]+f[v][1])%mod,mod-2)%mod,t1=t*fpow(f[v][0],mod-2)%mod;
        g[v][0]=(s1+t1)%mod;
        g[v][1]=s1%mod;
        //cout<<f2[v][1]<<" "<<f2[v][0]<<endl;
        dfsg(v,u);
    }
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>u[i]>>v[i];
		add(u[i], v[i]);
		add(v[i], u[i]);
	}
	dfsf(1, 0);
	g[1][1]=1;
	g[1][0]=1;
	dfsg(1, 0);
	for(int i=1;i<n;i++)
	{
		if(dep[u[i]]>dep[v[i]])
		{
			swap(u[i], v[i]);
		}
		ans=(f[v[i]][1]+f[v[i]][0])%mod*f[u[i]][1]%mod*fpow(f[v[i]][0],mod-2)%mod*g[u[i]][1]%mod;
		ans%=mod; 
		ans+=f[v[i]][1]*f[u[i]][0]%mod*fpow(f[v[i]][1]+f[v[i]][0], mod-2)%mod*g[u[i]][0]%mod;
		cout<<ans%mod<<endl;
	}
	return 0;
}

T4

感谢dyc、dzb、lyh、wsq几位大佬潜心研究。

\(\mathtt{2024/2/22}\)

累了，歇会儿在写

鸽子来填坑了

\(\mathtt{2024/4/5}\)

T1 聪明的燕姿

首先，一个小学奥数教过的东西：

设\(n\)为一个不为素数的自然数，则\(n\)可以表示为：$ p_{1}{a_{1}}*p_{2}{a_{2}}*p_{3}{a_{3}}*...*p_{k}{a_{k}}\((其中\)p[i]$为质因数）。

那么\(n\)的约数和S为：

然后发现枚举选了哪些质数，以及这些质数的指数，等于得到了\(x\)，判断\(S\)是否符合条件即可。(用搜索枚举）

搜索需要三个参数，\(now\)，\(x\)，\(s\)，分别表示：还剩多少能够分解，当前枚举第\(x\)个质数，当前是哪个数。

此时，搜索需满足两个条件，就可以得到答案：

1、若当前数\(now\)可表示成一个并未搜索过的质数与\(1\)的和\((\)设这个质数为\(p\)，其实就是\(p^{0}+p^{1}\) \()\)，则\(s\)与\(p\)的乘积可以成为答案。

2、\(now=1\)，即当前的数不能再分解。则当前的数\(s\)可以成为答案.

（全部引用）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int s, cnt;
int k, a[maxn], p[maxn], st[maxn];
bool prime(int x)
{
	if(x==1) return 0;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0) return 0;
	}
	return 1;
}
void dfs(int now,int x,int s)
{
	if(now==1)
	{
		a[++cnt]=s;
		return ;
	}
	if(prime(now-1)&&p[x]<now)
	{
		a[++cnt]=s*(now-1);
	}
	for(int i=x;p[i]*p[i]<=now;i++)
	{
		int t=p[i];
		int num=p[i]+1;
		for(;num<=now;t*=p[i],num+=t)
		{
			if(now%num==0)
			{
				dfs(now/num,i+1,s*t);
			}
		}
	}
}
int main()
{
	st[1]=1;	
	for(int i=2;i<=100000;i++)//线性筛 
	{
		if(!st[i])
		{
			p[++k]=i;
		}
		for(int j=1;j<=k&&p[j]*i<=100000;j++)
		{
			st[p[j]*i]=1;
			if(i%p[j]==0) break;
		}
	} 
	while(~scanf("%d",&s))
	{
		memset(a,0,sizeof(a));
		cnt=0;
		dfs(s, 1, 1);
		cout<<cnt<<endl;
		sort(a+1, a+cnt+1);
		for(int i=1;i<=cnt;i++)
		{
			cout<<a[i]<<" ";
		}
		if(cnt) cout<<endl;
	}
	return 0;
}

T2 收集邮票

一道概率题。

设 \(dp[i]\) 表示已经收集了
\(i\) 种邮票，还需要花费的钱数的期望。\(num[i]\) 表示已经收集了 \( i\) 种邮票，还需要购买的次数的期望。

考虑 \(dp[i]\) 和 \(num[i]\) 是由两种情况得来：买到了已经买过的和买到了没有买过的。

  • 买到了已经买过的：\(num[i]=(num[i]+1)*\displaystyle\frac{i}{n}\).
  • 买到了没有买过的：\(num[i]=(num[i+1]+1)*\displaystyle\frac{n-i}{n}\).

化简得 \(num[i]=\displaystyle\frac{num[i+1]*\frac{n-i}{n}+1}{1-\frac{i}{n}}\)

同理：\(dp[i]=\displaystyle\frac{dp[i+1]*\frac{n-i}{n}+num[i]*\frac{i}{n}+num[i+1]*\frac{n-i}{n}+1}{1-\frac{i}{n}}\)

\(dp[0]\) 即为答案。

#include<bits/stdc++.h>
using namespace std;
int n;
double dp[10005], num[10005];
int main()
{
	cin>>n;
	for(int i=n-1;i>=0;i--)
	{
		num[i]=((num[i+1])*(n-i)*1.0/n+1)*1.0/(1-i*1.0/n);
		dp[i]=(dp[i+1]*(n-i)*1.0/n+num[i]*i/n+num[i+1]*(n-i)/n+1)/(1-i*1.0/n);
	}
	printf("%.2lf",dp[0]);
	return 0;
}

T3 苹果树

题解

#include<bits/stdc++.h>
#define int long long
const int maxn=2005;
using namespace std;
int n, p;
int dp[maxn][maxn], fac[10005];
long long ans;
signed main()
{
	cin>>n>>p;
	fac[0]=1;
	for(int i=1;i<=n;i++)
	{
		fac[i]=1ll*fac[i-1]*i%p;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			dp[i][j]=(dp[i-1][j-1]*j%p+1ll*dp[i-1][j]*(i-j-1)%p)%p;
		}
		dp[i][1]=(dp[i][1]+fac[i])%p;
	}
	for(int i=1;i<=n;i++)
	{
		ans=(ans+1ll*dp[n][i]%p*i*(n-i))%p;
	}
	printf("%lld",ans%p);
	return 0;
}

T4 高速公路

一篇让我豁然开朗的题解

其实这个思路挺暴力的，但又挺巧妙的。

#include <iostream>
#include <cstdio>
#define lid id << 1
#define rid id << 1 | 1
#define ll long long
using namespace std;
const ll maxN=100000+7;
ll gcd(ll a,ll b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
ll sum1, sum2, sum3, n, m, l, r, v;
struct seg_tree{
   ll l, r;
   ll sum[6], lazy;
   ll mx;
}tr[2000005]; 
void pushup(int id)
{
	tr[id].sum[1]=tr[lid].sum[1]+tr[rid].sum[1];
	tr[id].sum[2]=tr[lid].sum[2]+tr[rid].sum[2];
	tr[id].sum[3]=tr[lid].sum[3]+tr[rid].sum[3];
}
void build(ll l,ll r,ll id) 
{
    tr[id].l=l;tr[id].r=r;
    if(l==r) 
	{
        tr[id].sum[4]=l*l;
        tr[id].sum[5]=l;
        return ;
    }
    ll mid=(l+r)>>1;
    build(l, mid, lid);
    build(mid+1, r, rid);
    tr[id].sum[4]=tr[lid].sum[4]+tr[rid].sum[4];
    tr[id].sum[5]=tr[lid].sum[5]+tr[rid].sum[5];
    return ;
}
void p(ll id,ll k) 
{
    tr[id].sum[1]+=(tr[id].r-tr[id].l+1)*k;
    tr[id].sum[2]+=k*tr[id].sum[5];
    tr[id].sum[3]+=k*tr[id].sum[4];
    tr[id].lazy+=k;
}
void pushdown(ll id) 
{
    p(lid, tr[id].lazy);
    p(rid, tr[id].lazy);
    tr[id].lazy=0;
    return ;
}
void add(ll l,ll r,ll id,ll val) 
{
	pushdown(id);
    if(tr[id].l>=l&&tr[id].r<=r) 
	{
        p(id,val);
        return ;
    }
    ll mid=(tr[id].l+tr[id].r)>>1;
    if(mid>=l) add(l, r, lid, val);
    if(mid<r) add(l, r, rid, val);
    pushup(id);
    return ;
}
void query(ll l,ll r,ll id) 
{
	pushdown(id);
    if(tr[id].l>=l&&tr[id].r<=r)  
	{
        sum1+=tr[id].sum[1];
        sum2+=tr[id].sum[2];
        sum3+=tr[id].sum[3];
        return ;
    }
    ll mid=(tr[id].l+tr[id].r)>>1;
    if(mid>=l) query(l, r, lid);
    if(mid<r) query(l, r, rid);
}
int main()
{   
    char s[3];
    cin>>n>>m;
    build(1,n,1);
    while(m--) 
	{
        scanf("%s",&s);
        cin>>l>>r;
        if(s[0]=='C') 
		{
            cin>>v;
            add(l, r-1, 1, v);
        }
        else 
		{
            ll a;
            sum1=sum2=sum3=0;
            query(l, r-1, 1);
            a=(r-r*l)*sum1+(r-1+l)*sum2-sum3;
            ll b=(r-l+1)*(r-l)/2;
            ll g=gcd(a,b);
            printf("%lld/%lld\n", a/g,b/g);
        }
    }
    return 0;
}

\(\mathtt{2024/5/2}\)

又双叒叕给大家垫底

考试时T1大模拟写了一半心态炸了，就去看其他题，主打一个不会，乱搞了42分回来，看来还要多锻炼代码能力。

T1 时间复杂度

就是纯模拟。\(O(1)\) 的时间复杂度就相当于 \(n^0\), 所以就是判断次方和语法问题了。用栈存储变量名，判断是否ERR。记得将字符串转变为整数。注意细节即可。

题解

#include<bits/stdc++.h>
using namespace std;
int T, l;
string s,s1[105];
int change(int &t, string s)//把字符串转变为整数 
{
	while(s[t]<'0'||s[t]>'9'&&t<s.size())
	{
		if(s[t]=='n') 
		{
			t++;
			return 1000000;
		}
		t++;
	}
	int sum=0;
	while(s[t]>='0'&&s[t]<='9')
	{
		sum=sum*10+s[t]-48;
		t++; 	
	}	
	return sum;
}
int check()
{
	int now=0,ans=0;
	stack<char> q;
	bool tmp[30]={0}, v[30]={0};
	int flag=0;
	for(int i=1;i<=l;i++)
	{
		if(s1[i][0]=='F')
		{
			int k=s1[i][2]-'a';
			q.push(k);
			if(tmp[k]) return -1;
			tmp[k]=1;
			int x=0, y=0, j;
			int tmp=4;
			x=change(tmp, s1[i]);
			y=change(tmp, s1[i]);
			if(y-x>10000)
			{
				if(flag==0)
				{
					now++;
					ans=max(ans,now);
					v[k]=1;
				}
			}
			if(x>y)
			{
				if(flag==0)
					flag=k;
			}
		}
		else
		{
			if(q.empty()) return -1;
			int t=q.top();
			q.pop();
			tmp[t]=0;
			if(flag==t) flag=0;
			if(v[t]==1)
			{
				v[t]=0;
				now--;
			}
		}
	}
	if(q.size()) return -1;
	return ans;
}
int main()
{
	cin>>T;
	while(T--)
	{
		scanf("%d ",&l);
		getline(cin, s);
		int x=3;
		int res=0;
		if(s[2]=='n')
		{
			res=change(x, s); 
		} 
		else res=0;
		for(int i=1;i<=l;i++)
		{
			getline(cin,s1[i]);
		}
		int t=check();
		if(t==-1) cout<<"ERR"<<endl;
		else if(t==res) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

T2 Emiya 家今天的饭

考虑逆推。（别问我为什么不是正推） 算出总共的方案数，再减去每列不超过限制这一条件限制的方案数。所以要求的就是任意列选的节点超过所有选的节点的一半的方案数之和。

考虑dp。设 \(dp[i][j][k]\) 表示前 \(i\) 行选 \(j\) 个节点，当前枚举到的列选 \(k\) 个节点的方案数。时间复杂度为 \(O(mn^3)\), 考虑优化。

可以发现\(k>⌊\displaystyle\frac {j}{2}⌋\) 这个式子可以转变为 \(2k+n-j>n\) ,\(n-j\) 其实就是这 \(n\) 行里没有选的行数（因为一行里只能选一个）。然后就有一个思路：

对于每个节点，选它时当做该列选了两次，而对于某一行不选时，当做所有列选了一次，最终要找的就是当前列被选超过 \(n\) 次的方案。这样就成功地优化掉了第二维。

状态转移方程：

  • 不选当前列：\(dp[j][k]=(dp[j][k]+dp[j-1][k]*(s[j]-a[j][i]))\)%\(mod\).
  • 不选当前行：\(dp[j][k+1]=(dp[j][k+1]+dp[j-1][k])\)%\(mod\).
  • 选当前行当前列对应的节点:\(dp[j][k+2]=(dp[j][k+2]+dp[j-1][k]*a[j][i])\)%\(mod\).
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n, m, a[105][3005], dp[105][3005], s[3005], g[3005], ans=1;
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			s[i]+=a[i][j];
			s[i]%=mod;
		}
		ans*=(s[i]+1)%mod;
		ans%=mod;
	}
	for(int i=1;i<=m;i++)
	{
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(int j=1;j<=n;j++)
		{
			for(int k=0;k<=2*(j-1);k++)
			{
				dp[j][k]=(dp[j][k]+dp[j-1][k]*(s[j]-a[j][i]))%mod;
				dp[j][k+1]=(dp[j][k+1]+dp[j-1][k])%mod;
				dp[j][k+2]=(dp[j][k+2]+dp[j-1][k]*a[j][i])%mod;
			}
		}
		for(int j=n+1;j<=2*n;j++)
		{
			ans=(ans+mod-dp[n][j])%mod;
		}
	}
	cout<<(ans+mod-1)%mod;
	return 0;
}

T3 凉凉

\({\color{CornflowerBlue} 颓，不想写了}\)

题解

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
int n, m, d[20][100005], a[20][100005],dp[20][100005],sum;//dp:前i深度，修建的铁路线状态为j的最小花费
int cnt[100005], vis[20][20], st[20], g[20][100005], cost[20][100005];
void init()//巨多的预处理
{
	for(int i=1;i<=n;i++)
	{
		sort(a[i]+1, a[i]+cnt[i]+1);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			vis[i][j]=vis[j][i]=1;//
			int x=1, y=1;
			while(x<=cnt[i]&&y<=cnt[j])
			{
				if(a[i][x]==a[j][y])
				{
					vis[i][j]=vis[j][i]=0;
					break;//不能在同一条线路上 
				}
				if(a[i][x]<a[j][y]) x++;
				else if(a[i][x]>a[j][y]) y++;
			}
		}
	}
	for(int s=1;s<=(1<<n)-1;s++)///枚举所有状态
	{
		int top=0;
		for(int i=1;i<=n;i++)
		{
			if(s&(1<<(i-1)))
			{
				st[++top]=i;
				for(int j=1;j<top;j++)
				{
					if(!vis[i][st[j]])
					{
						for(int k=1;k<=n;k++)
						{
							g[k][s]=inf;
						}			
					}
				}
				if(dp[1][s]==inf) break;
				for(int j=1;j<=n;j++)
				{
					g[j][s]+=cost[i][j];
				}
			}
		}
	} 
	for(int s=0;s<=(1<<n)-1;s++)
	{
	 	dp[1][s]=g[1][s];
	}
	return ;
} 
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>d[i][j];
		} 
	}
	for(int i=1;i<=n;i++)
	{
		cin>>cnt[i];
		for(int j=1;j<=cnt[i];j++)
		{
			cin>>a[i][j];
		}
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=cnt[i];k++)
			{
				cost[i][j]+=d[j][a[i][k]];//预处理每一个深度j建立铁路线i花费的价格 
			}
		}
	}
	init(); 
	for(int i=2;i<=n;i++)
	{
		for(int s=0;s<(1<<n);s++)
		{
			dp[i][s]=dp[i-1][s];
			for(int s1=s;s1;s1=(s1-1)&s)
			{
				dp[i][s]=min(dp[i][s], dp[i-1][s^s1]+g[i][s1]);
			}
		}
	}
	cout<<dp[n][(1<<n)-1]<<endl;
	return 0;
}
/*
6 6
146535743 658514039 110666795 34504724 85525675 189578100
58729011 145246168 699341967 82610526 85807179 305216637
58874454 435729044 466564966 295434213 32774319 32446331
223562722 66903639 232162498 232607761 7701608 18168855
333930316 101806612 231078532 256376010 219095862 679656625
270951932 79253958 261137115 376445683 33791012 285869973
3 6 3 2
3 6 3 2
6 4 3 2 6 1 5
6 6 2 3 5 4 1
2 6 1
1 3

*/

\(\mathtt{2024/5/3}\)

寄！大寄特寄！

考试时估分\({\mathtt{165}}\)，觉得自己能打的分都打出来了。结果：\({\mathtt{165->95}}\), 我真的。。。

讲个笑话，做T2时，觉得像是状压dp，然后定义了一个这个：\({\color{red}dp[31][5000010]}\);
但是脑抽的我并没有注意到它\({\color{red}RE}\)了。其次，我有一个很不好的习惯，就是复制粘贴，T2和T4的两个代码全都是粘T2代码改的！！！只能说，还好是模拟赛，否则我就像CSP-J一样惨了！！！

T1 Stack of Presents

很暴力的思想，也没啥好说的，直接放代码吧：

#include<bits/stdc++.h>
using namespace std;
int t;
long long n,m,ans=0,maxn=0;
long long p[100005], a[100005], b[100005];
int main()
{
	cin>>t;
	while(t--)
	{
		int x;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			p[a[i]]=i;
		}
		for(int i=1;i<=m;i++)
		{
			cin>>b[i];
			if(p[b[i]]<maxn)
			{
				ans++;
			}	
			else
			{
				ans+=2*(p[b[i]]-i)+1;
				maxn=p[b[i]];
			}
		}
		cout<<ans<<endl;
		ans=0, maxn=0;
	}
	return 0;
}

T2 棠梨煎雪

看了篇题解回来，感觉简单了不少？？

T3 打砖块

考试时觉得这个题比T2简单，打了一个区间dp，\({\mathtt{45}}\)分：

//打部分分 区间dp 
#include<bits/stdc++.h>
using namespace std;
const int maxn=200+10;
int T, n, m, K, dp[maxn][maxn], sum[maxn][maxn], f[maxn][maxn];
//dp[i][j]表示前i列用j发子弹能达到的最高分 
//sum[i][j]表示第i列用j发子弹能达到的最高分 
char c[maxn][maxn];
int main()
{
	cin>>n>>m>>K;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>f[i][j]>>c[i][j];
		}
	}
	for(int i=1;i<=m;i++)
	{
		int k=n;
		for(int j=1;j<=K;j++)//k为行数，每次竖着打 
		{
			if(k>0)
			{
				sum[i][j]=sum[i][j-1]+f[k][i];	
			} 
			k--;
		} 
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=K;j++)
		{
			for(int k=0;k<=j;k++)//枚举子弹数量 
			{
				dp[i][j]=max(dp[i][j],dp[i-1][k]+sum[i][j-k]);
			}
		}
	}
	cout<<dp[m][K];
	return 0;
}

然后题解思路大概和这个代码差不多：在设dp状态时应多考虑一维，考虑最后一发子弹打到 ‘Y’ 还是 ‘N’ 上，转移方程有一点像区间（背包？）dp，自己推导一下即可。

然后有这么一个思路：借子弹

假设现在有这么两列砖块：

第一列: (底部)|N|N|N|N|(顶部)

第二列: (底部)|N|N|N|N|Y|Y|(顶部)

现在我们有8发子弹,要考虑怎么打能拿到最高分。

因为我们知道打Y能获得一发子弹，所以就尽可能打Y。但是假如已经打完这两列的N，就已经没有子弹了，所以我们就要留一发子弹。
在打第一列的时候，留着最后一个N不打，然后先去打第二列，打到Y，这样手里就多了两发子弹，最后再去打第一列剩余的，就可以获得更多的分数。

题解

\({\mathbb{DZB}}\)大佬的题解

#include<bits/stdc++.h>
using namespace std;
const int maxn=200+10;
int T, n, m, K, dp[maxn][maxn][2], sumy[maxn][maxn], sumn[maxn][maxn], f[maxn][maxn];
char c[maxn][maxn];
int main()
{
	cin>>n>>m>>K;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>f[i][j]>>c[i][j];
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1, w=n;j<=min(n,K)&&w>0;j++, w--)
		{
			if(c[w][i]=='N')
			{
				sumy[i][j]=sumy[i][j-1]+f[w][i];
				sumn[i][j]=sumy[i][j];
			}
			else
			{
				sumy[i][--j]+=f[w][i];
			}
		} 
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<=K;j++)
		{
			for(int k=0;k<=j;k++)
			{
				dp[i][j][0]=max(max(dp[i-1][j-k][0],dp[i-1][j-k][1])+sumy[i][k],dp[i][j][0]);
				if(k>0)
					dp[i][j][1]=max(dp[i-1][j-k][0]+sumn[i][k],dp[i][j][1]);
				if(k<j)
					dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-k][1]+sumy[i][k]);
			}
		}
	}
	cout<<dp[m][K][1];
	return 0;
}

T4 斗地主

一个暴力搜索，顺序如下图：

然后就是大模拟。。。

#include<bits/stdc++.h>
using namespace std;
int T, n, ans, t[25];
void dfs(int x) 
{
	if(x>=ans) return;
	int k=0; 
	for(int i=3;i<=14;i++) 
	{
		if(t[i]==0) k=0;   
		else
		{
			k++;   
			if(k>=5) 
			{
				for(int j=i;j>=i-k+1;j--) 
					t[j]--; 
				dfs(x+1); 
				for(int j=i;j>=i-k+1;j--) 
					t[j]++;  
			}
		}
	}
	k=0; 
	for(int i=3;i<=14;i++)
	{
		if(t[i]<=1) k=0;
		else 
		{
			k++;
			if(k>=3)
			{
				for(int j=i;j>=i-k+1;j--) 
					t[j]-=2; 
				dfs(x+1);
				for(int j=i;j>=i-k+1;j--) 
					t[j]+=2;  
			}
		}
	}
	k=0; 
	for(int i=3;i<=14;i++)
	{
		if(t[i]<=2) k=0;
		else 
		{
			k++;
			if(k>=2)
			{
				for(int j=i;j>=i-k+1;j--) 
					t[j]-=3;
				dfs(x+1);
				for(int j=i;j>=i-k+1;j--) 
					t[j]+=3;
			}
		}
	}
	for(int i=2;i<=14;i++) 
	{
		if(t[i]<=3)
		{
			if(t[i]<=2) continue;
			t[i]-=3;  
			for(int j=2;j<=15;j++)   
			{
				if(t[j]<=0||j==i) continue; 
				t[j]--; 
				dfs(x+1);
				t[j]++;  
			}
			for(int j=2;j<=14;j++)    
			{
				if(t[j]<=1||j==i) continue; 
				t[j]-=2;
				dfs(x+1);
				t[j]+=2;  
			}
			t[i]+=3;  
		} 
		else
		{
			t[i]-=3;
			for(int j=2;j<=15;j++)   
			{
				if(t[j]<=0||j==i) continue;
				t[j]--;
				dfs(x+1);
				t[j]++;
			}
			for(int j=2;j<=14;j++)     
			{
				if(t[j]<=1||j==i) continue;
				t[j]-=2;
				dfs(x+1);
				t[j]+=2;
			}
			t[i]+=3;
			t[i]-=4; 
			for(int j=2;j<=15;j++)   
            {
				if(t[j]<=0||j==i) continue; 
				t[j]--; 
				for (int k=2;k<=15;k++) 
				{
					if(t[k]<=0||j==k) continue;
					t[k]--; 
					dfs(x+1);
					t[k]++;  
				}
				t[j]++;  
			}
			for(int j=2;j<=14;j++)  
			{
				if(t[j]<=1||j==i) continue;
				t[j]-=2;    
				for(int k=2;k<=14;k++) 
				{
					if(t[k]<=1||j==k) continue;
					t[k]-=2; 
					dfs(x+1);
					t[k]+=2;  
				}
				t[j]+=2;  
			}
			t[i]+=4;  
		}
	}
	for(int i=2;i<=15;i++) 
	{
		if(t[i]) x++;
	}
	ans=min(ans, x);
}
int main()
{
	cin>>T>>n;
	while(T--)
	{
		ans=0x3fffffff;
		memset(t, 0, sizeof(t));
		for(int i=1;i<=n;i++)
		{
			int x, y;
			cin>>x>>y;
			if(x==0) t[15]++;
			else if(x==1) t[14]++;
			else t[x]++; 
		}
		dfs(0);
		cout<<ans<<endl;
	}
	return 0;
}

\(\mathtt{2024/5/19}\)

怎么越考越难啊？心态已经要炸了。

T1 Color

\(dp[i]\) 表示当前有 \(i\) 个某种颜色的球（假设为 \(A\) ）变到所有球颜色都为 \(A\) 的期望步数。

\(dp[0]=0, dp[n]=0\),状态转移方程为：

\[dp[i]=1/p[i]+1/2*dp[i-1]+1/2*dp[i+1] 。 \]

通过边界值可以 \(O(n)\) 推出式子：\(dp[n-1]=k[n-1]*dp[n]+b[n-1]\)，然后回代。

但是这是一个条件概率，\((i+1)\) 个 \(A\) 和 \((i-1)\) 个 \(A\) 达到颜色全部为 \(A\) 的概率是不同的（分别是 \((i+1)/2n\) 和 \((i-1)/2n\)) 。

所以可以理解成在 \(2i\) 种结果中平均有 \((i+1)\) 次从 \(i\) 个 \(A\) 球变成 \((i+1)\)个 \(A\) 球，有 \((i-1)\) 次从 \(i\) 个球变成\((i-1)\)个$ A$ 球。
方程为：

\[dp[i]=1/p[i]+(i-1)/(2i)*dp[i-1]+(i+1)/(2i)*dp[i+1] \]

最后汇总即可 。

liu_runda - 博客园 题解

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
string s;
int t[maxn], len;
double p[maxn], g[maxn], k[maxn], sum, dp[maxn], b[maxn];
int main()
{
	cin>>s;
	len=s.size();
	for(int i=1;i<=len;i++)
	{
		for(int j=1;j<=len;j++)
		{ 
			char c;
			cin>>c;
		}
	}
	for(int i=0;i<len;i++)//统计每个字母的个数 
	{
		t[s[i]-'A']++;
	}
	for(int i=1;i<len;i++)
	{
		g[i]=(len*(len-1))*1.0/(2*i*(len-i));
	}
	dp[len]=0, k[1]=1, b[1]=g[1];
	for(int i=2;i<len;i++)
	{
		k[i]=(i+1)*1.0/(2*i);
		k[i]=k[i]*1.0/(1-k[i-1]*(i-1)*1.0/(2*i));
		b[i]=b[i-1]*(i-1)/2.0/i+g[i]; 
		b[i]=b[i]/(1-k[i-1]*(i-1)/2.0/i);
	}
	for(int i=len-1;i>=1;i--)//因为是回代，所以要逆序
	{
		dp[i]=k[i]*dp[i+1]+b[i];	
	} 
	for(int i=0;i<26;i++)
	{
		sum+=t[i]*1.0/(double)len*dp[t[i]];	
	}
	printf("%.1lf", sum);
	return 0;
}

T2 SSY的队列

有一个状压思路（真的很好想）：\(dp[i][s]\) 表示最后一个数的下标为 \(i\) ，前面的状态为 \(s\) 的方案数。转移方程是每次枚举新加入的人，然后每一个新方案加上原来没有加入新人的方案数（记得判断）。最后求和。

70pts：

//先试着打一下70分的状压 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1234567891;
int n, a[35], m, sum;
int dp[1005][1<<15];//表示最后一个数为i(的下标),前面的状态为s的方案数 
int b[35][35];//标注哪两个数的差值为m的倍数 
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	cin>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<i;j++)
		{
			if(abs(a[i]-a[j])%m==0)
				b[i][j]=b[j][i]=1;
		}
	} 
	for(int i=0;i<n;i++)
	{
		dp[i][1<<i]=1;	
	} 
	for(int i=1;i<=(1<<n)-1;i++)
	{
		for(int j=0;j<n;j++)
		{
			if((1<<j)&i)//这一位为1 
			{
				for(int k=0;k<n;k++)//枚举新加入的人 
				{
					if((1<<k)&i) continue;
					if(b[j+1][k+1]==0)
					{
						dp[k][i|(1<<k)]=(dp[k][i|(1<<k)]+dp[j][i])%mod;
					}
				}
				
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		sum+=dp[i][(1<<n)-1];
		sum%=mod;
	}
	cout<<sum;
	return 0;
}

但有且仅有70分。

∴正解

正解思路十分奇妙,我们观察题目的描述,意思是所有对M余数相等的数是不可放在一起的.
那么我们可以将所有的数以余数分类,再进行处理.
可知:

  1. 同类数不可以放在一起,但是同类数的位置均可对调.
  2. 我们定义的某个状态的种类数,事实取决于某个状态不同种类的不同剩余个数的情况.

第二条是较难归纳出的,我们来看一个浅显的例子:
2233 这四个数进行排列的种类数与 4455 这四个数排列的情况数是一致的.

状压为什么会炸,因为它存了很多没有用的状态而且也访问并转移了许多没有用的状态.
同时因为它没有类别之分,就会导致很多时候它的一些状态是已经访问过的,但状压无法辨识.

如此看状压已经没有优化空间,但是状压的思路我们要留着.

接着看如何实现.

我们根据上述规律去走一遍 \(dfs\) ,只不过这次不是单纯的暴力模拟了,我们加入了记搜,状压,以及 \(hash\) 成分.

为什么还有hash呢,因为我们想想, \(dfs\) 依旧以着 \(dp\) 的思路在跑.
然而我们的 \(dp\) 描述状态要各个数余下的种类以及最后一个数是哪一种的(因为明显我们是不可以把两个同种的放在一起的).
但是它有三十个数,所以明显咱们不能开三十维.

那就要借助一个 \(hash\) 的思想,将状态压成一个 \(ull\) 的数,同时用 \(map\) 将这个数映射到一个可以操作的下标上.
这样就能保证转移有效,省去空间,同时得到正解.

题解

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int mod=1234567891, P=131;
int n, a[35], m, ans;
int cnt, num[50], t[50], maxn, v[50], p[50];
int b[35][35];//标注哪两个数的差值为m的倍数
map<ull, int> mp[50];
int dfs(int x,int last)//last表示最后一个数是哪一种的 
{
	if(x>n) return 1;
	memset(t,0,sizeof(t));
	for(int i=1;i<=cnt;i++)
	{
		if(i^last)
		{
			t[num[i]]++;
		}
	}
	ull k=num[0];
	for(int i=1;i<=maxn;i++)
	{
		k=k*P+t[i];
	}
	k=k*P+num[last];
	if(mp[x].find(k)!=mp[x].end())
	{
		return mp[x][k];
	}
	int tmp=0;
	if(num[0])
	{
		num[0]--;
		tmp=(tmp+dfs(x+1, 0))%mod;
		num[0]++;
	}
	for(int i=1;i<=cnt;i++)
	{
		if((i^last)&&num[i])
		{
			num[i]--;
			tmp=(tmp+dfs(x+1, i))%mod;
			num[i]++;
		}
	}
	return mp[x][k]=tmp;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	cin>>m;
	for(int i=1;i<=n;++i)
		a[i]=(a[i]%m+m)%m;
	for(int i=1;i<=n;i++)
	{
		if(v[i]) continue;
		v[i]=1;
		int count=0;
		for(int j=i;j<=n;j++)
		{
			if(a[i]^a[j]) continue;
			v[j]=1, count++;
		}
		maxn=max(maxn, count);
		if(count==1)
		{
			num[0]++;
		}
		else
		{
			num[++cnt]=count;
		}
	}
	p[0]=1;	
	maxn=max(maxn, num[0]);
	for(int i=1;i<=maxn;i++)
	{
		p[i]=p[i-1]*i%mod;
	}
	ans=1;
	for(int i=0;i<=cnt;i++)
	{
		ans=ans*p[num[i]]%mod;
	}
	ans*=dfs(1, 0);
	ans%=mod;
	cout<<ans;
	return 0;
}

T3

TJ

T4 小铃的烦恼

同T1。不放代码了，占地方。

\(\mathtt{2024/6/2}\)

update on: 6. 6 回来填坑了

考完试后，心态莫名有些炸，一直鸽了4天，总感觉自己概率期望学得不好，一定要好好刷题啊。

T1 等差子序列

考试只会写30pts的暴力，下考后发现思路相反了，应该枚举差值，否则常数太大,会超时。

考虑枚举第一个数和差值，就可以固定第二三个数，判断位置关系即可。

//思路反了，应该枚举差值 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
std::bitset<1000> bs;
int T, n;
int a[10005], pos[10005];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),	cout.tie(0);
	cin>>T;
	while(T--)
	{
		memset(pos, 0, sizeof(pos));
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			pos[a[i]]=i;
		}
		bool flag=0;
		for(int i=1;i<=n;i++)
		{
			for(int c=(1-i)/2;c<=(n-i)/2;c++)//枚举差值
			{
				if(pos[i]<pos[i+c]&&pos[i+c]<pos[i+c*2]) 
				{
					cout<<"Y"<<endl;
					flag=1;
					break;
				}
			} 
			if(flag) break;
		}
		if(!flag) cout<<"N"<<endl;
		flag=0;
	}
	return 0;
}

T2 非诚勿扰

又是概率题

概率期望+树状数组优化。

会发现一个女生选中k个男生的概率可以用等比数列求和。

然后就是一个树状数组求逆序对对问题了。

\(vector\) 的用法

题解

#include<bits/stdc++.h>
#define ld long double
#define lowbit(x) (x&(-x))
using namespace std;
const int maxn=5e5+100;
int n, m, a, b;
ld P, sum[maxn], ans;
void add(int x,ld v)
{
	while(x<maxn)
	{
		sum[x]+=v;
		x+=lowbit(x);
	}
}
ld query(int x)
{
	ld ans=0;
	while(x)
	{
		ans+=sum[x];
		x-=lowbit(x);
	}
	return ans;
}
vector<int> v[maxn];
int main()
{
	cin>>n>>m>>P;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		v[a].push_back(b);
	}
	for(int i=1;i<=n;i++)//对于集合中的男生按编号排序 
	{
		sort(v[i].begin(), v[i].end());
	}
	for(int i=1;i<=n;i++)
	{
		if(!v[i].size()) continue;//非空
		int siz=v[i].size();
		for(int j=0;j<siz;j++)
		{
			ld p=pow(1-P, j)*P/(1-pow(1-P, siz));
			ans+=p*(query(n)-query(v[i][j]));
			add(v[i][j], p);
		}  
	}
	printf("%.2Lf",ans);
	return 0;
}

T3 括号序列

考虑设一个三维 \(dp\) (显然是区间 \(dp\) )。

其中第三位表示不同形态，共五六种：

  1. 全部是 \(*\)。
  2. 左右被括号(左右括号匹配)包裹。
  3. 左边括号序列开头，右边 \(*\) 结尾。
  4. 与2相反。
  5. 两边括号序列开头结尾。
  6. 两边 \(*\) 开头结尾 。

然后考虑转移，最终答案为 \(dp[1][n][4]\)。

题解

改这道题的心路历程：看洛谷第一篇题解。（这个状态设计也tql）感觉如果是自己，考场上大概率是想不出来的。仔细分析一下，除去区间dp，剩余的部分就是将题意描述的合法区间转移过来（有包含关系），其实说白了就是要考虑全面。状态设定真的是dp最重要的部分之一。然后就是转移方程，注意提前判断是否合法，转移的时候也要注意是否合法，将要算的转化为已有的，还有就是区间dp思想，其实也没什么太大难点。不过我自己按照题解的思路打了半天，结果一大堆细节不一样，果然还是太菜。好好锻炼思维能力和代码能力。

//考虑设一个三维dp(显然是区间dp)
//其中第三位表示不同形态，共五种：
//0：全部是 *
//1：左右被括号(左右括号匹配)包裹
//2：左边括号序列开头，右边 * 结尾
//3：与2相反
//4：两边括号序列开头结尾
//5：两边 * 开头结尾 
//然后考虑转移，最终答案为 dp[1][n][4]
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn=505, p=1e9+7;
int n, k, dp[maxn][maxn][6];
char a[maxn];
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		dp[i][i-1][0]=1;
	}
	for(int l=1;l<=n;l++)
	{
		for(int i=1;i<=n-l+1;i++)
		{
			int j=i+l-1;
			//枚举转移
			if(l<=k&&(a[j]=='*'||a[j]=='?'))
			{
			//	cout<<1;
				dp[i][j][0]=dp[i][j-1][0]%p;
			} 
			if(l>=2)
			{
				if((a[i]=='('||a[i]=='?')&&(a[j]==')'||a[j]=='?'))
				{//四种情况：全 * ，一边是 * ，两边都不是 *  
					dp[i][j][1]=(dp[i+1][j-1][0]+dp[i+1][j-1][2]+dp[i+1][j-1][3]+dp[i+1][j-1][4])%p;
				}
				//然后就是区间dp思想，枚举断点相乘
				for(int k=i;k<j;k++)
				{
					dp[i][j][2]=(dp[i][j][2]+dp[i][k][4]*dp[k+1][j][0])%p;
					dp[i][j][3]=(dp[i][j][3]+(dp[i][k][3]+dp[i][k][5])*dp[k+1][j][1])%p;
					dp[i][j][4]=(dp[i][j][4]+(dp[i][k][2]+dp[i][k][4])*dp[k+1][j][1])%p; 
					dp[i][j][5]=(dp[i][j][5]+dp[i][k][3]*dp[k+1][j][0])%p;
				} 
			}
			dp[i][j][4]=(dp[i][j][1]+dp[i][j][4])%p; //包含1
			dp[i][j][5]=(dp[i][j][0]+dp[i][j][5])%p;//包含0 
		}
	}
	cout<<dp[1][n][4]%p;
	return 0;
}

T4 围栏障碍训练场

感觉是逆推。

\(dp[i][0/1]\) 表示从第 \(i\) 个围栏左/右端点向下走 到原点的最短距离。

\(dp[i][0/1]=min(dp[j][0/1]+d)\) ( \(d\) 表示 \(i\) 的左右端点和 \(j\) 的左右端点的距离）。

线段覆盖，用线段树维护。

题解

 
#include<bits/stdc++.h>
#define ll long long
#define lid id<<1
#define rid id<<1|1
using namespace std;
const int N=2e6+5, M=2e5+2, P=1e5+1;
int n, s, a[N], b[N], tr[800005];
ll dp[N][2];
void update(int id, int l, int r, int ql, int qr, int v) 
{
	if(ql<=l&&r<=qr) 
	{
		tr[id]=v; 
		return; 
	}
	int mid=(l+r)>>1;
	if(ql<=mid) 
	{
		update(lid, l, mid, ql, qr, v);
	}
	if(mid<qr) 
	{
		update(rid, mid+1, r, ql, qr, v);
	}
}
int query(int id, int l, int r, int x) 
{
	if(l==r) 
	{
		return tr[id];	
	}
	int mid=(l+r)>>1;
	if(x<=mid) 
	{
		return max(tr[id], query(lid, l, mid, x));
	} 	
	else
	{
		return max(tr[id], query(rid, mid + 1, r, x));	
	} 	
}
int main()
{
	cin>>n>>s;
	s+=P;
	a[0]=b[0]=P;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		a[i]+=P, b[i]+=P;
	}
	for(int i=1;i<=n;i++)
	{
		int l=query(1, 1, M, a[i]);
		int r=query(1, 1, M, b[i]);
		dp[i][1]=min(dp[r][1]+abs(b[r]-b[i]), dp[r][0]+abs(a[r]-b[i]));
		dp[i][0]=min(dp[l][1]+abs(b[l]-a[i]), dp[l][0]+abs(a[l]-a[i])); 
		update(1, 1, M, a[i], b[i], i);
	}
	cout<<min(dp[n][1]+abs(b[n]-s),dp[n][0]+abs(a[n]-s));
	return 0;
}

\(\mathtt{2024/6/9}\)

膜你赛。四道dp，非常友好。

已经不在乎分数了。

T1 小奇挖矿2

考试时想都没想的基础dp：

//应该是dp 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n;
ll a, b, ans=0, m;
ll s[N], dp[N], v[N], maxn;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a>>b;
		s[b]=a;
		maxn=max(b, maxn);
	}
	dp[0]=s[0];
	v[0]=v[4]=v[7]=1;
	for(int i=4;i<=maxn;i++)
	{
		if(i-7>=0&&v[i])
		{
			dp[i]=max(dp[i-4], dp[i-7])+s[i];
			v[i+4]=v[i+7]=1;
		}
		else if(v[i])
		{
			dp[i]=dp[i-4]+s[i];
			v[i+4]=v[i+7]=1;
		}
	}
	for(int i=1;i<=maxn;i++)
	{
		ans=max(ans, dp[i]);
	}
	cout<<ans;
	return 0;
}

期望得分：60pts

实际得分：30pts

为什么呢？因为这里有个细节：s[b]+=a;

它的位置是可以重复的。痛失30pts。

正解：

通过赛瓦维斯特定理或者列表/暴算可发现：

所有大于17的数字都可以由4和7凑出来。

原本的dp占了太大空间（ \(m\) ≤1e9），就考虑缩小这个空间。

考虑将任意两个距离大于18的星球的距离改为18，重新计算每一个星球的长度，剩下的就是朴素dp了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
int a, b, ans=0, m, t;
int s[N*20], dp[N*20], d[N], maxn;
pair<int,int> p[N]; 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a>>b;
		p[i]=make_pair(b, a);
	}
	memset(dp,-0x3f,sizeof(dp));
	dp[0]=0;
	sort(p+1, p+n+1);
	for(int i=1;i<=n;i++)
	{
		d[i]=min(18, p[i].first-p[i-1].first);
	}
	for(int i=1;i<=n;i++)
	{
		t+=d[i];//长度 
		s[t]+=p[i].second;
	}
	for(int i=4;i<=t;i++)
	{
		if(i-7>=0)
		{
			dp[i]=max(max(dp[i], dp[i-4]), dp[i-7])+s[i];
		}
		else
		{
			dp[i]=max(dp[i], dp[i-4])+s[i];
		}
	}
	for(int i=1;i<=t;i++)
	{
		ans=max(ans, dp[i]);
	}
	cout<<ans;
	return 0;
}

题解

T2 小奇的矩阵(matrix)

考场上式子推出来了，二维dp想到了，死活写不出来。

首先，把题上的式子进行化简，就变成了这个样子（过程就不说了）：

\[(n+m-1)*\sum\limits_{i=1}^{n+m-1}a_i^2-\sum\limits_{i=1}^{n+m-1}a_i \]

然后考虑定义一个三维dp数组，\(dp[i][j][k]\) 表示到第\((i,j)\)这个位置，总和为 \(k\) ，存储的是最小平方和。

剩下的转移方程就很简单了。

#include<bits/stdc++.h>
using namespace std;
int T, n, m, t, sum, num;
int a[35][35], b[35][35];
int dp[35][35][2000];
long long ans=1e9; 
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		t=n+m-1;
		int maxn=(n+m)*30;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cin>>a[i][j];
			}
		}
		memset(dp, 127, sizeof(dp));
		dp[1][1][a[1][1]]=a[1][1]*a[1][1];
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(i==1&&j==1) continue;
				for(int k=a[i][j];k<=maxn;k++)//枚举的是和 
				{
					dp[i][j][k]=min(dp[i-1][j][k-a[i][j]], dp[i][j-1][k-a[i][j]])+a[i][j]*a[i][j];
				}
			}
		}	
		long long ans=1e9;
		for(int k=0;k<=maxn;k++)
		{
			if(dp[n][m][k]!=dp[0][0][0])
				ans=min(ans, (long long)dp[n][m][k]*t-k*k);
		}
		cout<<ans<<endl;
	}
	return 0;
}

题解

T3 小奇的仓库(warehouse)

考场上拿到这道题：哇！直接用lca求树上两点距离能骗到30分呢（太久T3没有拿到分了）。然后疯狂开写。

下考场：啊？这是换根dp？！

30pts：树形换根dp（不考虑异或）

非常简单的dp式子( \(sum\) 数组表示最终要求的值）：

\[sum[v]=sum[u]-size[v]*w+(n-size[v])*w \]

分子树内部和子树外部考虑。不会的自己画一棵树。

正解：定义 \(f[i][j]\) 表示走到点 \(i\) ，值为 \(j\) 的路径个数。

那么在没有异或的情况下，显然有：\(f[u][j+w]+=f[v][j]\)( \(w\) 为 \(u,v\) 之间的边权）。

会发现 \(m\) 不大于15，那么它数值改变的只有后四位，其他位置就是上面30pts的那个式子。所以其实就只用考虑 \((j+w)\%16\) 这部分。在换根的情况下，要反过来处理，即： \(f[v][(j+w)\%16]+=f[u][j]\),但是由于一个父节点有许多子节点，所以要另开一个数组保存。

//30pts:树形换根dp
//正解：f[i][j]表示走到点i，值为j的路径个数
//分开考虑异或和换根
//异或；发现只对后四位有影响，整除16的部分可以按没有异或的换根dp处理，%16的部分有一定枚举范围
//换根：f数组要反向把值传递给自己的儿子，注意要多开一个数组保存 
//就俩 dfs 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+1;
int n, m;
int ans, sum[maxn];
int edgenum, head[maxn], dis[maxn], f[maxn][17], a[17], size[maxn];
//sum:要求的值，dis:每个点距树根的值 size:子树大小 
struct edge{
	int next;
	int w;
	int to;
}edge[maxn<<1];
inline void add(int from, int to, int w)
{
	edge[++edgenum].next=head[from];
	edge[edgenum].to=to;
	edge[edgenum].w=w;
	head[from]=edgenum;
}
inline void dfs(int u,int fa)
{
	f[u][0]=1;
	size[u]=1;
	sum[1]+=dis[u];
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to, w=edge[i].w;
		if(v==fa) continue;
		dis[v]=dis[u]+w;
		dfs(v, u);
		size[u]+=size[v];
		for(int j=0;j<16;j++)
		{
			f[u][(j+w)%16]+=f[v][j];
		}
	}
}
inline void dfs1(int u,int fa)
{
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to, w=edge[i].w;
		if(v==fa) continue;
		//           ↓子树内部    ↓子树外部 
		sum[v]=sum[u]+(n-2*size[v])*w;//无异或情况
		memset(a, 0, sizeof(a));
		for(int j=0;j<16;j++)
		{
			a[(j+w)%16]=f[u][(j+w)%16]-f[v][j];//f[u][]数组还要给其他儿子使用 		
		}
		for(int j=0;j<16;j++)
		{
			f[v][(j+w)%16]+=a[j];
		}
		dfs1(v, u); 
	}
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<n;i++)
	{
		int x, y, z;
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x, y, z);
		add(y, x, z);
	}
	dfs(1, 0);
	dfs1(1, 0);
	for(int i=1;i<=n;i++)
	{
		f[i][0]--;
		for(int j=0;j<16;j++)
		{
			int k=(j^m);
			sum[i]+=((k-j)*f[i][j]);//记得异或 
		}
		printf("%lld\n",sum[i]);
	}
	return 0;
}

把我一个蒟蒻讲懂的题解

p.s.因为数组开大查了半个小时没出来，真的就是一个玄学啊。

T4 Kamp

讲个笑话，wsq推荐我做这道题练习 \(up\,and\,down\), 然后我把它放在任务计划里将近半年，没有做一点。。。

渐渐理解了。

首先，常规套路，换根dp，俩dfs。

定义： 表示以 \(u\) 根的子树中从 \(u\) 开始把子树内的人送回家并回到 \(u\) 节点的最短路程。 \(f[u]\) 表示把整棵树的人送回家并回到 \(u\) 节点的最短路程。

\(len1[u]\) 数组表示最长链，\(len2[u]\) 数组表示次长链。

这里先讲一下次长链是怎么更新的：

首先找出能更新最长链的路径，用 \(len2\) 数组保存原有最长链的值（此时它就是第二长的了），然后再更新 \(len1\) 数组。注意每次更新是用else if连接的，所以这两个数组的值不会相同。

第一个dfs：处理g数组。

处理出子树内的人数、最长链和次长链。

\[g[u]+=g[v]+2*w; \]

void dfs(int u,int fa)//处理子树内部的最长链、次长链、g数组 
{
	if(p[u]) s[u]=1;
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to, w=edge[i].w;
		if(v==fa) continue;
		dfs(v, u);
		s[u]+=s[v]; 
		if(s[v])
		{
			g[u]+=g[v]+2*w;//往返2次 
			int l=len1[v]+w;	
			if(l>=len1[u])
			{
				len2[u]=len1[u];
				len1[u]=l;
				id[u]=v;	
			}	
			else if(l>=len2[u]) len2[u]=l;
		}
	}	
}

第二个dfs，处理f数组：

void dfs1(int u,int fa)
{
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to, w=edge[i].w;
		if(v==fa) continue;
		if(s[v]==0) 
		{
			f[v]=f[u]+2*w;
			len1[v]=len1[u]+w;
		}
		else if(k-s[v]==0) f[v]=g[v];
		else if(k-s[v])
		{
			f[v]=f[u];
			if(len1[u]+w>=len1[v]&&id[u]!=v)
			{
				len2[v]=len1[v];
				len1[v]=len1[u]+w;
				id[v]=u;	
			}
			else if(len2[u]+w>=len1[v])
			{
				len2[v]=len1[v];
				len1[v]=len2[u]+w;
				id[v]=1;	
			}//更新最长链 
			else if(len1[u]+w>=len2[v]&&id[u]!=v)
			{
				len2[v]=len1[u]+w;
			}
			else if(len2[u]+w>=len2[v])
			{
				len2[v]=len2[u]+w;
			}//更新次长链 
		}
		dfs1(v, u);
	 } 
}

代码

//up and down
//g[u]表示以u为根的子树中从u开始把子树内的人送回家并回到u节点的最短路程
//f[u]表示把整棵树的人送回家并回到u节点的最短路程
//两个dfs处理好上面两个数组后，答案即为f[u]-len1[u] 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e5+5;
int n, k, a[maxn];
int g[maxn], f[maxn];
int ans;
int s[maxn], p[maxn], id[maxn], len1[maxn], len2[maxn];
//s[u]为u子树内有几个人 
struct edge{
	int next, to, w;
}edge[maxn<<1];
int head[maxn], edgenum;
void add(int from,int to,int w)
{
	edge[++edgenum].next=head[from];
	edge[edgenum].to=to;
	edge[edgenum].w=w;
	head[from]=edgenum;
}
void dfs(int u,int fa)//处理子树内部的最长链、次长链、g数组 
{
	if(p[u]) s[u]=1;
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to, w=edge[i].w;
		if(v==fa) continue;
		dfs(v, u);
		s[u]+=s[v]; 
		if(s[v])
		{
			g[u]+=g[v]+2*w;//往返2次 
			int l=len1[v]+w;	
			if(l>=len1[u])
			{
				len2[u]=len1[u];
				len1[u]=l;
				id[u]=v;	
			}	
			else if(l>=len2[u]) len2[u]=l;
		}
	}	
} 
void dfs1(int u,int fa)
{
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to, w=edge[i].w;
		if(v==fa) continue;
		if(s[v]==0) 
		{
			f[v]=f[u]+2*w;
			len1[v]=len1[u]+w;
		}
		else if(k-s[v]==0) f[v]=g[v];
		else if(k-s[v])
		{
			f[v]=f[u];
			if(len1[u]+w>=len1[v]&&id[u]!=v)
			{
				len2[v]=len1[v];
				len1[v]=len1[u]+w;
				id[v]=u;	
			}
			else if(len2[u]+w>=len1[v])
			{
				len2[v]=len1[v];
				len1[v]=len2[u]+w;
				id[v]=1;	
			}//更新最长链 
			else if(len1[u]+w>=len2[v]&&id[u]!=v)
			{
				len2[v]=len1[u]+w;
			}
			else if(len2[u]+w>=len2[v])
			{
				len2[v]=len2[u]+w;
			}//更新次长链 
		}
		dfs1(v, u);
	 } 
}
signed main()
{
	cin>>n>>k;
	for(int i=1;i<n;i++)
	{
		int x, y, z;
		cin>>x>>y>>z;
		add(x, y, z);
		add(y, x, z);
	}
	for(int i=1;i<=k;i++) 
	{
		int x;
		cin>>x;
		p[x]=1;
	}
	dfs(1, 0);
	f[1]=g[1]; 
	dfs1(1, 0); 
	for(int i=1;i<=n;i++)
	{
		cout<<f[i]-len1[i]<<endl;
	}
	return 0;
}

P.S.鸽了很久才写，好多想说的都忘了，十分抱歉。

题解

这个八种分类讨论属实把我震撼到了。

以后的总结见考试心得2。

标签：int,ll,cin,long,maxn,考试,心得,dp
From： https://www.cnblogs.com/zhouyiran2011/p/18369386

相关文章

  • 金蝶云苍穹应用开发初级认证考试
    本文内容为：金蝶苍穹开发初级认证考试原题单选题1.界面规则不可以实现以下哪项效果：DA.根据条件控制单据上某个字段的显示隐藏B.根据条件控制单据某个字段是否必录C.根据条件控制单据上某个字段的锁定性D.根据条件控制单据列表单元格的颜色2.以下关于界面插件说法正......
  • 【Vue】考试功能实现
    一、需求场景 最近临时加的一个功能模块，让我两天就实现.... 部门成员需要进行测验考试，简单来说就是刷题练习 关于题库导入的部分在这篇文章已经写好了：https://www.cnblogs.com/mindzone/p/18362194 分值计算的需求目前没加入进来，只判断对错与否，然后计数题目总数和做对题数......
  • 关系代数、函数依赖、Armstrong公理及软考试题解析
    注：本文面向于软考高级—系统架构设计师，具体来说是数据库部分，知识点偏零碎化。想要系统学习数据库原理的，可考虑去看《数据库原理》，清华大学出版社或其他出版社皆可。概述概念关系，就是二维表。特性：列不可分性：关系中每一列都是不可再分的属性，即不能出现如下复合属性行列无序性：......
  • 8.15 考试反思
    8.15考试反思T1P2434区间求多个线段的的交。由题意得，对于任意两条线段来说，关系有三种：一条在另一条内部，为重合。一条线段和另一条有接触的部分，称为相接。一条与另一条完全无接触部分，称为相间。于是可得：当我们发现两条线段重合时，舍去较短的一条如果发现有相接的线段，我......
  • [考试记录] 2024.8.17 csp-s模拟赛21
    T1Set解析思考+组合题场上只能想到暴力01背包再加上bitset优化，很好打。本应该有60pts（？或者更多），不曾想由于spj的一些未知原因喜提systemerror，全部cancelled。喜提0pts。......
  • 基于flask+vue框架的的在线考试系统[开题+论文+程序]-计算机毕设
    本系统（程序+源码+数据库+调试部署+开发环境）带论文文档1万字以上，文末可获取，系统界面在最后面。系统程序文件列表开题报告内容研究背景随着信息技术的飞速发展和互联网的普及，教育领域正经历着前所未有的变革。传统考试模式，尽管在评估学生学习成果方面发挥着重要作用，但其组织......
  • java+vue计算机毕设基于Web的在线考试管理信息系统【源码+开题+论文】
    本系统（程序+源码）带文档lw万字以上文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着信息技术的飞速发展和教育改革的不断深入，传统考试模式已难以满足现代教育的需求。在线考试作为一种新兴的教育评估方式，凭借其便捷性、高效性和灵......
  • [lnsyoj2271/luoguP3745/省选联考 2017]期末考试
    题意给定长度为\(n\)的序列\(t\)和长度为\(m\)的序列\(b\)，以及常数\(A,B,C\)，可以进行两种操作：选取任意\(1\lex,y\len\)，并使\(b_x+1,b_y-1\)，记进行了\(\alpha\)次这种操作；选取任意\(1\lez\len\)，并使\(b_z-1\)，记进行了\(\beta\)次这种操作。求进......
  • 考研数学模拟考试
         欧几里得8月模考正式开始报名了，走过路过千万不要错过，这是各位小伙伴检验复习成果、提升实力的大好机会哦，接下来是考试的一些信息：首先是所有小伙伴都会关心的一个问题，那就是考试收费吗？答案是考试全程免费，无隐性收费。参与模考、批改处分、直播解析等各个环节......
  • 自建开源学习考试系统-moodle4.02
    注意：本文档是关于在使用PHP7.4的Ubuntu20.04服务器中安装Moodle4.021、安装ubuntu20.04LTS服务器版，记得安装时使用国内源如http://mirrors.aliyun.com/ubuntu安装vimsudoapt-getinstallvim2、安装Apache/MySQL/PHPsudoaptinstallapache2mysql-clientmysq......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99