題解

#1. 納西妲

我們注意到這個題和平時 OI 中對中位數的定義不太一樣。這個題中偶數個數的中位數是排序后中間兩個里較大的那一個。然后我們就發現一個長度為 \(2\) 的區間操作后較小的值會變成較大的值。由于可以無限次操作，我們可以將整個序列都變成其最大值，這樣答案就是整個序列的最大值。

ll n,a,mx;
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	while(n--){
		cin>>a;
		mx=max(mx,a);
	}
	cout<<mx;
	return 0;
}

#2. 琳妮特

考慮 \(k=10\) 的情況。

一般來說小學應該會講到如何判定一個數能否被 \(9\) 整除：將各數位上的數加起來看這個和能不能被 \(9\) 整除。

注意到數的位數非常大（就像在題面中說的一樣）所以盲猜一把和數的位置沒啥關系，聯系剛才 \(k=10\) 的結論，我們大膽猜測直接把 \(k\) 進制下各數位加起來看能不能被 \((k-1)\) 整除就行。證明：

• 由于 \(k\equiv 1\pmod {(k-1)}\)，\(k^2\equiv k(k-1)+k\equiv k \equiv 1\pmod{(k-1)}\)，所以對于任意的 \(n \in \mathbb{N}\) 我們有 \(k^n\equiv\pmod{(k-1)}\)。
• 因此，如果第 \(p\in\mathbb{N^+}\) 位上是 \(a\)，那么該位對整個數模 \((k-1)\) 的值的貢獻就是 \(ak^{p-1}\equiv a\pmod{(k-1)}\)。
• 于是剛才的結論成立。

ll t,n,s,a,u,v,w,k;
int main(){
	cin>>t;
	while(t--){
		cin>>n>>k;
		s=0;
		while(n--){
			cin>>a>>u>>v>>w;
			s+=a;
			s%=k-1;
		}
		if(s)cout<<"No";
		else cout<<"Yes"; 
		cout<<endl;
	} 
	return 0;
}

#3. 阿貝多

大模擬不講。

注意由于修改次數太多，我們需要給所有的化學式開 set 然后二分查找。計算化學式量時對于括號可以直接遞歸。其他問題請參考代碼。

struct node{
	//化學式、化學式量
	string s;
	ll m;
};
bool operator<(node x,node y){
	return x.s<y.s;
}
string st[]={"H","He","Li","Be","B","C","N","O","F","Ne","Na","Mg","Al","Si","P","S","Cl","Ar","K","Ca","Sc","Ti","V","Cr","Mn","Fe","Co","Ni","Cu","Zn","Ga","Ge","As","Se","Br","Kr","Rb","Sr","Y","Zr","Nb","Mo","Tc","Ru","Rh","Pd","Ag","Cd","In","Sn","Sb","Te","I","Xe","Cs","Ba","La","Ce","Pr","Nd","Pm","Sm","Eu","Gd","Tb","Dy","Ho","Er","Tm","Yb","Lu","Hf","Ta","W","Re","Os","Ir","Pt","Au","Hg","Tl","Pb","Bi","Po","At","Rn","Fr","Ra","Ac","Th","Pa","U","Np","Pu","Am","Cm","Bk","Cf","Es","Fm","Md","No","Lr","Rf","Db","Sg","Bh","Hs","Mt","Ds","Rg","Cn","Uut","Fl","Uup","Lv","Uus","Uuo"};
ll m[]={10,40,69,90,108,120,140,160,190,202,230,243,270,281,310,321,355,400,391,401,450,479,509,520,549,559,589,587,636,654,697,726,749,790,799,838,855,876,889,912,929,960,980,1011,1029,1064,1079,1124,1148,1187,1218,1276,1269,1313,1329,1373,1389,1401,1409,1442,1450,1504,1520,1573,1589,1625,1649,1673,1689,1730,1750,1785,1809,1838,1862,1902,1922,1951,1970,2006,2044,2072,2090,2090,2100,2220,2230,2260,2270,2320,2310,2380,2370,2440,2430,2470,2470,2510,2520,2570,2580,2590,2620,2650,2680,2710,2720,2700,2760,2810,2800,2850,2840,2890,2880,2930,2920,2940};
ll op,p,pp,b[200];
set<node> a;
node TMP[10010];
ll calc(string s,ll l,ll r){//計算化學式量 
	if(r<l)return 0;
	ll sum=0;
	for(int i=l;i<=r;i++){
		if(s[i]=='('){//有括號就遞歸 
			ll tmp=i+1,cnt=1;
			while(tmp<=r&&cnt>0){//找到括號右端點 
				if(s[tmp]=='(')cnt++;
				if(s[tmp]==')')cnt--;
				tmp++;
			}
			if(cnt!=0){
				return -1;
			}
			ll ttmp=calc(s,i+1,tmp-2);
			if(ttmp==-1){
				return -1;
			}
			while(s[tmp]>='0'&&s[tmp]<='9'){//處理下標 
				cnt*=10;
				cnt+=s[tmp]-'0';
				tmp++;
			}
			sum+=ttmp*max(cnt,1ll);
			i=tmp-1;
			continue;
		}
		if(s[i]>='A'&&s[i]<='Z'){//判非大寫開頭 
			ll tmp=i+1,cnt=0;
			string ttmp="";
			ttmp+=s[i];
			while(tmp<=r&&s[tmp]>='a'&&s[tmp]<='z'){//根據大小寫找到完整的元素符號 
				ttmp+=s[tmp];
				tmp++;
			}
			ll flg=0;
			for(int j=0;j<118;j++){//暴力判斷該符號是否存在 
				if(ttmp==st[j]){
					flg=j+1;
					break;
				}
			}
			if(!flg){
				return -1;
			}
			flg--;
			while(s[tmp]>='0'&&s[tmp]<='9'){//處理下標 
				cnt*=10;
				cnt+=s[tmp]-'0';
				tmp++;
			}
			sum+=m[flg]*max(cnt,1ll);
			i=tmp-1;
		}
		else{
			return -1;
		}
	}
	return sum;
}
bool check(string s,string t){//暴力查找 s 中是否含有元素 t 
	for(int i=0;i<=s.length()-t.length();i++){
		if(s[i]!=t[0])continue;
		bool flg=1;
		for(int j=0;j<t.length();i++,j++){
			if(s[i]!=t[j]){
				flg=0;
				break;
			}
		}
		if(flg&&(s[i]<'a'||s[i]>'z'))return 1;
		i--;
	} 
	return 0;
}
void add(string s,ll op){//加入統計信息 
	bool flg[120]={};
	for(int i=0;i<s.length();i++){
		if(s[i]<'A'||s[i]>'Z')continue;
		string ss="";
		ss+=s[i++];
		while(s[i]>='a'&&s[i]<='z')ss+=s[i++];
		for(int j=0;j<118;j++){
			if(st[j]==ss){
				if(!flg[j]){
					flg[j]=1;
					b[j]+=op;
				}
				break;
			}
		}
		i--;
	}
}
void query(){
	ll mm;
	pp=0;
	string s[20];
	cin>>mm;
	for(int i=0;i<mm;i++){//判斷元素是否存在 
		cin>>s[i];
		bool flg=0;
		for(int j=0;j<118;j++){
			if(st[j]==s[i]){
				flg=1;break;
			}
		}
		if(!flg){
			cout<<"Invalid.\n";
			pp=-1;
			return ;
		}
	}
	for(set<node>::iterator i=a.begin();i!=a.end();i++){//遍歷 set 中的每個位置 
		bool flg=0;
		for(int j=0;j<mm;j++){
			if(!check((*i).s,s[j])){
				flg=1;
				continue;
			}
		}
		if(!flg){
			TMP[pp++]=(*i);
		}
	}
	cout<<pp<<" formula(s) are founded.\n";
	pp=min(50ll,pp);
	for(int i=0;i<pp;i++){
		cout<<i+1<<" - "<<TMP[i].s<<'('<<TMP[i].m/10.0<<')'<<endl;
	} 
}
int main(){
	while(1){
		cin>>op;
		if(op==0)return 0;//退出 
		if(op==1){//插入 
			string s;
			cin>>s;
			bool flg=0;
			for(set<node>::iterator i=a.begin();i!=a.end();i++){//判重 
				if((*i).s==s){
					flg=1;
					break;
				}
			}
			if(flg){
				cout<<"Repeat.\n";
				continue;
			}
			ll tmp=calc(s,0,s.length()-1);//計算與判定合法 
			if(tmp==-1){
				cout<<"Invalid.\n";
				continue;
			}
			a.insert({s,tmp});
			add(s,1);
			cout<<'='<<tmp/10.0<<".\n";
			continue;
		}
		if(op==2){//刪除 
			cin>>op;
			if(op){//調用查找模塊 
				query();
				if(pp==-1)continue;
				ll tmp;
				cout<<"Type a number:";
				cin>>tmp;
				if(tmp>0&&tmp<=pp){
					add(TMP[tmp-1].s,-1);
					a.erase(a.lower_bound(TMP[tmp-1]));
					cout<<"Successfully.\n";
				}
				else cout<<"Invalid.\n";
				continue;
			}
			string s;
			cin>>s;
			set<node>::iterator tmp=a.lower_bound({s,0});//在 set 中找到字符串 
			if(tmp==a.end()||(*tmp).s!=s)cout<<"Not found.\n";
			else{
				add((*tmp).s,-1);
				a.erase(tmp);
				cout<<"Successfully.\n";
			}
			continue;
		}
		if(op==3){//查找 
			query();
			continue;
		}
		if(op==4){//統計 
			cout<<"In general:"<<a.size()<<endl;
			for(int i=0;i<118;i++){
				if(b[i]){
					cout<<st[i]<<':'<<b[i]<<endl;
				}
			}
			continue;
		}
	}
	return 0;
}

#4. 溫　迪

本題最大的難度是發現它是圖論。

我們看到每個限制條件是兩首歌在相鄰的節目，這種條件很大可能是建邊來轉化成圖論問題。于是我們給每一個條件建雙向邊。

然后先判定是否有解。注意到有邊相連的節點由于是相鄰的節目，所以場次奇偶性一定不同，然后進行黑白染色看能否成功即可。

接著求最多的節目數量。由于路徑上相鄰兩點的節目編號之差的絕對值為 \(1\)，所以我們只需要找到一對點，使其間最短路徑最長，這個路徑所包含的點數就是答案。

另外原題保證了圖連通，而本題并沒有保證。注意到不同連通塊之間完全不影響，我們將各連通塊分別計算然后把答案加起來就行了。如果直接 copy 原題代碼，只能得到至多 \(20\) 分，因為我往每個包（除了連通的包）里都塞了一組 hack。

ll n,vis[2010],v[2010],dis[2010],ans,flg,mx;
ll u;
vector<ll> a[2010];
void work(ll now){
	mx=0;//當前連通塊內的答案 
	memset(v,0,sizeof(v));//記錄本連通塊內的點集 
	vis[now]=1;//1/2染色方案 0表示沒染 
	v[now]=1;
	queue<ll> q;
	q.push(now);
	while(!q.empty()){//BFS 進行染色 
		ll tmp=q.front();
		q.pop();
		for(int i=0;i<a[tmp].size();i++){
			if(!vis[a[tmp][i]]){
				vis[a[tmp][i]]=3-vis[tmp];
				v[a[tmp][i]]=1;
				q.push(a[tmp][i]);
			}
			else if(vis[a[tmp][i]]==vis[tmp]){
				flg=1;
				return ;
			}
		} 
	}
	for(int i=1;i<=n;i++){//枚舉每個點 
		if(!v[i])continue;
		memset(dis,0,sizeof(dis));
		dis[i]=1;
		q.push(i);
		while(!q.empty()){//BFS 求到各點的距離 
			ll tmp=q.front();
			q.pop();
			for(int i=0;i<a[tmp].size();i++){
				if(!dis[a[tmp][i]]){
					dis[a[tmp][i]]=dis[tmp]+1;
					q.push(a[tmp][i]);
				}
			} 
		}
		for(int j=1;j<=n;j++){//求最大值 
			mx=max(mx,dis[j]);
		}
	}
	ans+=mx;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		ll tmp;
		cin>>tmp;
		while(tmp--){
			cin>>u;
			a[i].push_back(u);
			a[u].push_back(i);
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[i])work(i);
		if(flg){
			cout<<-1;
			return 0;
		}
	}
	cout<<ans;
	return 0;
}

反思

• T1 需要你在審題時發現題目中中位數的定義與平時所看到的略有不同。和去年一樣，提醒大家，只要看到異常的東西就應該引起注意。一些比較經典的：
  • 某變量的范圍小于 \(25\)。
  • 序列每一項的值域不是 \(10^9,10^{18},2^{31}-1,2^{63}-1\) 中的某一個，且不是 \(10^9\) 或 \(10^{18}\) 除以長度。
  • 操作次數等的范圍在 \(10^8\) 以上。
  • 數據范圍中出現了一些奇怪的式子，例如P8814 [CSP-J 2022] 解密。
  • 多種操作的題中對某類操作的次數做出單獨限制，例如P7910 [CSP-J 2021] 插入排序。
  • 一些東西的定義和常用的不一樣。
• T2 需要你注意到 \(k=10\) 的部分分并進行思考。類似于數學壓軸題，一道好的題目的部分分，尤其是特殊性質，通常能夠將思路向正解引領。同時也提醒大家不要放棄思考部分分，萬一寫到一半發現可以推廣成正解呢？
• T3 是大模擬題，考場上遇到此類題目建議先讀題并看數據范圍，找比較好寫的部分分（一般會有十幾二十幾分），防止寫不完。
• T4 主要是提醒大家不要想當然地以為一些東西。使用條件前先確定其是否存在。
• 最后提醒大家不要過于相信大樣例，之前有人跑過了所有大樣例但是最終 \(0\) 分。為此，本場的大樣例都比較弱。
  • T1 的大樣例最大值超過了一半。
  • T3 的大樣例刻意放過了 2 0 操作暴力查找的算法。
  • T4 的樣例中的圖全部連通。有解的大樣例是鏈。無解的大樣例是長為奇數的環。但正式數據每個包里都塞了一組不連通的，其中連通的部分是鏈，不連通的部分是三元環。（采納了 lhx 大佬的建議）

希望大家都能在 CSP J/S 2024 和 NOIP 2024 中取得好成績！我們考場見！