date: 2019-11-15
目錄- Day -1
- Day 0
- Day 1
- 考前
- 考中
- 考后
- 做法&程式（考場做法，不能AC）
- 格雷碼
- 題意
- 做法
- 程式
- 括號樹
- 題意
- 做法（理論50分，實際80分）
- 程式
- 樹上的數
- 題意
- 做法（10分）
- 程式
- 格雷碼
- Day 2
- 考前
- 考中
- 考后
- 做法&程式（考場做法，不能AC）
- Emiya 家今天的飯
- 做法（36分）
- 程式
- 劃分
- 做法（64分）
- 程式
- 樹的重心
- 想法（40分）
- 程式
- Emiya 家今天的飯
- Day 3+（后記&提醒）
前言：想直接進入正題請跳轉到Day 1，
Day -1
明天我就去南京了，感到非常的緊張，畢竟CSP和NOIP沒有關系，沒有真題可以刷（逃，
注：對于內心中難度的比較，是對于NOIP提高組的題目比較的，
Day 0
坐了一趟一個小時卻感覺像是一天的火車，終于到了南京，到了南京就去南航去報到，報到完了就去三食堂的二樓吃飯，比學校的飯菜要好吃（SAN值++），晚上和同學家長吃飯，互相鼓（mo）勵（bai）一番以排解壓力，回來之后寫寫線段樹（對的，我喜歡寫線段樹），只需要一點點時間就可以讓自己變得開心起來（大霧），
總的來說，在沒有被Day1血虐之前，我今天還是比較開心的，
Day 1
考前
進入考場沒有什么大問題，試機前半段時間腦抽，bits之類的板子和提醒自己的東西都好久才想起來打，后半段花了大半段時間在搞懂怎么提交（話說我好像曾經來打過一次比賽來著怎么忘了），導致自己沒有聽清試題電子檔的位置，心態瞬間跌入谷底，考前的提醒是放的NOIP2018的，很好笑，考場的人都笑了，稍稍緩解了氣氛，如果沒有的話心態肯定會受到影響（然后翻車），所以說，考前一定要有一個開心的心情，心態不能亂，
考中
開局先開T1，感覺難度還沒有什么問題，花了40分鐘仔仔細細地做了，后來又花了30分鐘檢查，才意識到即使開了ull也需要特判\(n=64\)的情況，并且把它加入了程式，
此時考試過去了1小時10分鐘，還剩2小時20分鐘，心態尚且正常，并未受到影響，T1 100分，
打開T2，T2很難，我想了大約30分鐘，想出了對于每一個結點都要維護從根節點到它的括號串中以它作為結束的子串的合法括號串個數，然后就不會做了，心想我先把T3的暴力分騙到了再來想T2的正解，于是我就開了T3，略微掃了一眼，幸好我比較菜（真的我沒有假），一看就不會做，然后花了30分鐘左右寫好了10分的暴力，
此時考試過去了2小時10分鐘，還剩1小時20分鐘，心態已經受到影響，T1 100分，T3 10分，
接下來的時間我都在做T2，由于題目難度激增，知道最后我都沒有把T2的正解寫出來，只能使用了一個簡單的優化策略，就是找一段最小的以它為結束的合法括號子串，之后把它開頭的父親結點的答案加1作為它的答案，這個優化即可騙到80分，雖然沒有寫出正解是個失誤，但是由于暴力寫得夠快常數夠小，并沒有造成太大影響，
考試結束，T1 100分，T2 當時估計70分，T3 10分
考后
出了考場，我先和同班同學交流了一下，發現他的預估分數是大約200分左右，當時心態就崩了，雖然現在發現他T1不僅沒有特判還寫錯了被卡成70分，T3爆零，但是對于當時的我來說，還是一個很大的沖擊，感覺自己鐵定與1=無緣了，
下午，令人驚訝的是，JS的程式很快就發了出來，同時信奧題庫上也可以自測了，自測出來是190分（驚奇的和最終分數一樣），比同學自測的還略高一點，重拾信心，
Day1結束后，我個人當時的心情應該還是OK的，沒有徹底灰心，不過經歷了一些大波動，腦海中還是會時不時的掠過諸如即將打鐵之類的想法，對于Day2還是有一定影響吧，，，（可能）
做法&程式（考場做法，不能AC）
格雷碼
題意
構造題，給出\(n\)和\(k\)，要求構造出\(n\)位格雷碼中的第\(k\)個，構造方法如下：（抄的題目啦）
-
\(1\)位格雷碼由兩個\(1\)位二進制串組成，順序為：\(0\)，\(1\)，
-
\(n+1\)位格雷碼的前\(2^n\)個二進制串，可以由依此演算法生成的\(n\)位格雷碼（總共\(2^n\)個\(n\)位二進制串）按順序排列，再在每個串前加一個前綴\(0\)構成，
-
\(n+1\)位格雷碼的前\(2^n\)個二進制串，可以由依此演算法生成的\(n\)位格雷碼（總共\(2^n\)個\(n\)位二進制串）按逆序排列，再在每個串前加一個前綴\(1\)構成，
做法
直接模擬即可，對于正在求的\(n\)位第\(k\)個字串，叫做\(f(n,k)\)，按照題目中的方式判斷：（從一開始標號）
\[f(n,k)='0'+f(n-1,k)(2k\leq n)\\ f(n,k)='1'+f(n-1,2^n-k)(2k\gt n) \]程式
記得特判一下\(n=64\)時的情況，此時會爆ull，但是由于要減一，所以可以賦值為\(-1\)來解決，
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
string ans;
void dfs(ull n,ull k){
if(n==0)return;
if(((ull(1))<<(n-1))>k){
ans+='0';
dfs(n-1,k);
}else{
ans+='1';
if(n==64){
ull tmp=-1;
tmp-=k;
dfs(n-1,tmp);
}else{
dfs(n-1,((ull(1))<<n)-k-1);
}
}
}
ull n,k;
int main(){
freopen("code.in","r",stdin);
freopen("code.out","w",stdout);
cin>>n>>k;
dfs(n,k);
cout<<ans<<endl;
return 0;
}
括號樹
題意
給你一棵\(1\)為根的樹，每個節點上面有一個括號，可能是(或者)， 定義\(s_i\)為：將根結點到\(i\)號結點的簡單路徑上的括號，按結點經過順序依次排列組成的字串， 要求出每一個結點的\(s\)中合法括號子串的個數，合法括號串定義見題目，
做法（理論50分，實際80分）
定義\(pre_i\)為以\(i\)作為結尾的\(s_i\)的合法括號子串的個數，
找到\(s_i\)后綴中最短的合法括號串，定義它的起始為\(l\)，結束為\(i\)，然后\(k_i\)就是\(k_{f(l)}+1\)（此處\(f(l)\)指的是\(l\)的父親），意義為后綴的最短合法串和之前的合法串連接后的也一定時合法的，也只有它們（和后綴最短合法串本身）是合法的，這個優化比樸素的查找所有的子串在隨機資料下要快得多，甚至會因為沒有開long long而WA而不是TLE，所以一定要記得開long long，即使它只是一個暴力，
程式
#include<bits/stdc++.h>
using namespace std;
struct NODE{
NODE *nxt;
int val;
NODE(){
nxt=NULL;
val=0;
}
};
struct LIST{
NODE *head,*tail;
LIST(){
head=new NODE;
tail=head;
}
void push(int val){
tail->val=val;
tail->nxt=new NODE;
tail=tail->nxt;
}
};
//后期注釋：自己實作鏈表以減小常數
typedef long long ll;
int n;
bool br[500005];
int f[500005];
LIST g[500005];
int ansk[500005];
//a grave for some code
//后期注釋：這個是我沒想出來的正解的紀念，代表我寫過
void brute(int x){
//后期注釋：計算pre
int brc=0,cur=x,cnt=0;
while(brc>=0&&cur){
brc+=(br[cur]?-1:1);
if(brc==0){
//后期注釋：優化
ansk[x]=ansk[f[cur]]+1;
break;
}
cur=f[cur];
}
for(NODE *it=g[x].head;it!=g[x].tail;it=it->nxt){
brute(it->val);
}
}
void calc(int x){
//后期注釋：簡單的把做法中的pre計算為k
ansk[x]+=ansk[f[x]];
for(NODE *it=g[x].head;it!=g[x].tail;it=it->nxt){
calc(it->val);
}
}
int main(){
freopen("brackets.in","r",stdin);
freopen("brackets.out","w",stdout);
scanf("%d\n",&n);
for(int i=1;i<=n;i++){
char c;
scanf("%c",&c);//cerr<<c<<' ';
br[i]=(c=='(');
}
f[1]=0;
for(int i=2;i<=n;i++){
scanf("%d",&f[i]);//cerr<<f[i]<<' ';
g[f[i]].push(i);
}
bool brt=false;
for(int i=2;i<=n;i++){
if(f[i]!=i-1)brt=true;
}
brute(1);
calc(1);
ll ans=0;
for(int i=1;i<=n;i++){
ans^=((ll)i)*ansk[i];
//cerr<<i<<": "<<ansk[i]<<endl;
}
printf("%lld",ans);
return 0;
}
樹上的數
題意
僅僅只需要注意一件事，這個是輸入輸出都是以數字排列的結點編號！
要好好看題目！不然很可能浪費做題時間！
做法（10分）
next_permutation()你值得擁有，它用于計算當前排列的下一個排列，
程式
#include<bits/stdc++.h>
using namespace std;
int T,n;
int eu[15],ev[15];
int a[15];
int o[15];
int v[15];
int r[15];
int tmp[15];
void solve(){
memcpy(v,o,sizeof(o));
for(int j=1;j<n;j++){
swap(v[eu[a[j]]],v[ev[a[j]]]);
}
//后期注釋：以邊的排列交換邊
for(int i=1;i<=n;i++){
tmp[v[i]]=i;
}
//后期注釋：改換為以數字排列的結點編號
for(int i=1;i<=n;i++){
if(tmp[i]<r[i]){
memcpy(r,tmp,sizeof(tmp));
break;
}
if(tmp[i]>r[i])break;
}
//后期注釋：更改最小字典序的排列
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>tmp[i];
o[tmp[i]]=i;
}
//后期注釋：讀入排列并更改為以結點編號排列的數字
memset(r,0x3f,sizeof(r));
for(int i=1;i<n;i++){
a[i]=i;
cin>>eu[i]>>ev[i];
}
//后期注釋：讀入邊同時初始化邊的排列
do{
//后期注釋：全排列需要交換的邊的順序
solve();
}while(next_permutation(a+1,a+n));
for(int i=1;i<=n;i++)cout<<r[i]<<' ';
cout<<endl;
}
return 0;
}
Day 2
考前
由于眾所周知的原因，我今天一開始就沒有想要做出任何一道題目的正解，換句話說，我今天就是沖著拿暴力分去的，這是一個看似慫實則更慫的方法，但是他很有用的，有的人死磕T1最后還沒搞出來，我還準備了一些糖果用于在昏昏沉沉的時候提神，事實證明這是有用的，
考中
這是我失策的一次，我全程T1T2T3換來換去，導致做題時間被分割成了大約半個小時的一段一段的，沒有集中精神思考，全部都只有基本暴力分，最后20分鐘還在改自己的程式，區域變數沒有初始化這種錯誤都會犯，幸好NOI LINUX的編譯器很好，把我的錯誤避免了，果然還是太緊張了，考試一定不能太緊張，由于時間分隔太多，對于每道題目的時間分配將在做法中寫出，
考后
考完了，心態什么樣都沒有關系了，滾回去刷題，
做法&程式（考場做法，不能AC）
Emiya 家今天的飯
做法（36分）
沒有想法，暴力搜索一波走，36分到手了，由于每一種烹飪方法的菜只有一種，所以就把這個當作是深度，每次選出一道就好了，程式好寫方便檢查，
程式
#include<bits/stdc++.h>
//后期注釋：無用頭檔案刪去
using namespace std;
/*
REMEMBER to use long long and unsigned long long
REMEMBER to check array size
REMEMBER to make brute-force program and use it
*/
typedef long long ll;
const int mod=998244353;
int n,m,k;
int a[105][2005];
int dfscnt[2005];
ll ans;
void dfs(int row,ll cur,int alr){
//后期注釋：row是遞回到第幾種烹飪方法，cur是目前方法數，alr是選了的菜的數量
if(alr==k){
ans=(ans+cur)%mod;
return;
}
//后期注釋：判斷是否制作了可行的組合，加入到答案里
if(n-row+1+alr<k){
return;
}
//后期注釋：可行性剪枝，然而并不能多騙一點分數，，，
for(int i=1;i<=m;i++){
if(dfscnt[i]<(k>>1)&&a[row][i]){
dfscnt[i]++;
dfs(row+1,cur*a[row][i]%mod,alr+1);
dfscnt[i]--;
//后期注釋：由于每一種食材、方法的菜都有很多種，所以直接乘上去它的數量可以多騙點分
}
}
dfs(row+1,cur,alr);
//后期注釋：判斷不選菜是否可行
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("meal.in","r",stdin);
freopen("meal.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(k=2;k<=n;k++){
//后期注釋：k是預備選的菜品的總數
dfs(1,1,0);
}
cout<<ans<<endl;
}
劃分
做法（64分）
首先，可以證明，確定了某一前綴區間的分配情況后，最后一個子任務盡量小答案才會好，不會證但是感性認識很簡單，考場時可以很快想到，我大約想了45分鐘想出這個結論，之后就是列舉子任務的大小DP就可以了，只需要寫20分鐘不到，區域變數千萬記得要初始化，我差點爆零，
程式
#include<bits/stdc++.h>
//后期注釋：無用頭檔案刪去
using namespace std;
//后期注釋：同上考前提醒，刪去
typedef long long ll;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
struct LIST{
//后期注釋：無用的鏈表，沒用上，完全錯誤的想法
};
int n,type;
int a[40000005];
ll dpf[5005];
ll dp[5005];
int dpprv[5005];
LIST tsk;
void specgen(){
//write no code, run nowhere
}
void normread(){
for(int i=1;i<=n;i++){
cin>>a[i];
}
}
void dp5000(){
ll ans;
//后期注釋：千萬記得要初始化，差點爆零
dp[0]=0;
//后期注釋：dp[i]表示直到i的前綴序列都計算好后最后一個子任務的長度最小是什么
for(int i=1;i<=n;i++){
dpf[i]=dpf[i-1]+a[i];
//后期注釋：前綴和計算
dp[i]=LLINF;
for(int j=0;j<i;j++){
if(dp[j]<=dpf[i]-dpf[j]&&dpf[i]-dpf[j]<dp[i]){
//后期注釋：列舉上一個前綴序列，發現更好的情況在轉移過去，記錄父親以便計算最后的答案（因為要算平方）
dp[i]=dpf[i]-dpf[j];
dpprv[i]=j;
}
}
}
int cur=n;
while(cur){
ans+=(dpf[cur]-dpf[dpprv[cur]])*(dpf[cur]-dpf[dpprv[cur]]);
cur=dpprv[cur];
//后期注釋：從最后一個結點n開始向著0更新
}
cout<<ans<<endl;
}
void greedy(){
//ohhhhhhhh f***
//i don't have time to complete it
//yet another grave here
//后期注釋：當時認為是貪心，后來發現是單調佇列，代碼沒寫
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("partition.in","r",stdin);
freopen("partition.out","w",stdout);
cin>>n>>type;
if(type){
specgen();
}else{
normread();
}
dp5000();
return 0;
}
樹的重心
想法（40分）
雖然好像做過原題，可是我忘了qaq，那么我就用樸素的方法，列舉樹的重心之后計算好了，就是程式寫起來很煩的樣子，其實還可以多騙一條鏈的15分的，就是我陣列開小了qaq，一定要檢查陣列啊，
程式
#include<bits/stdc++.h>
//后期注釋：無用頭檔案
using namespace std;
//后期注釋：同上提醒
typedef long long ll;
int RP,n,sz[2005],ban,f[2005];
vector<pair<int,int> > g[2005];
ll ans;
int find(int x){
if(f[x]==x)return x;
else return f[x]=find(f[x]);
}
void unite(int x,int y){
x=find(x);
y=find(y);
f[x]=y;
}
void dfs(int x,int p){
sz[x]=1;
for(int i=0;i<g[x].size();i++){
int y=g[x][i].first,z=g[x][i].second;
if(y!=p&&z!=ban){
dfs(y,x);
sz[x]+=sz[y];
}
}
//后期注釋：計算有根時它的子樹大小
}
void mkc(int x,int p){
bool isc=sz[find(x)]-sz[x]<=(sz[find(x)]>>1);
for(int i=0;i<g[x].size();i++){
int y=g[x][i].first,z=g[x][i].second;
if(y!=p&&z!=ban){
mkc(y,x);
isc&=sz[y]<=(sz[find(x)]>>1);
}
}
if(isc)ans+=x;
//后期注釋：查看是否是重心并加入答案
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("centroid.in","r",stdin);
freopen("centroid.out","w",stdout);
cin>>RP;
while(RP--){//后期注釋：RP--啦（不是）
cin>>n;
for(int i=1;i<=n;i++){
g[i].clear();
}
ans=0;
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
g[a].push_back(make_pair(b,i));
g[b].push_back(make_pair(a,i));
}
if(n%10==1){//后期注釋：特判鏈，可惜陣列開小了
for(int i=1;i<n;i++){
if(((1+i+1)>>1)==((1+i)>>1)){
ans+=(1+i)>>1;
}else{
ans+=(1+i);
}
if(((n+i+1+1)>>1)==((n+i+1)>>1)){
ans+=(n+i+1)>>1;
}else{
ans+=(n+i+1);
}
}
cout<<ans<<endl;
ans=0;
continue;
}
for(int bn=1;bn<n;bn++){//后期注釋：列舉洗掉的邊
int rt1=-1,rt2=-1;
ban=bn;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=n;i++){
for(int j=0;j<g[i].size();j++){
int k=g[i][j].first,l=g[i][j].second;
if(l!=ban)unite(i,k);
}
}
for(int i=1;i<=n;i++){
if(rt1==-1){
rt1=find(i);
}else{
if(rt1!=find(i)){
rt2=find(i);
break;
}
}
}//后期注釋：用并查集制作連通并找到兩個根
dfs(rt1,-1);
dfs(rt2,-1);
mkc(rt1,-1);
mkc(rt2,-1);
}
cout<<ans<<endl;
}
}
Day 3+（后記&提醒）
注意事項：
- 區域變數初始化
- 不要因為緊張而把時間分成一小段一小段
- 不要害怕難，大家都難（除非你像我一樣做題時不時腦抽）
- 陣列檢查一下，不能只檢查直接使用它的子任務，如果有陣列復用還要檢查復用了它的子任務是否會爆，
好像成績還行的樣子，326分1=，可以試著報各類WC誒（雖然去了也只是充人數），
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/117899.html
標籤：其他