NOIP 模擬賽 張若天 2018 年 10 ? 23 ? 題?名稱 監聽 實驗室 ?明 可執??件名 monitor lab civilization 輸??件名 monitor.in lab.in civilization.in 輸出?件名 monitor.out lab.out civilization.out 每個測試點時限 1 秒 1 秒 1 秒 內存限制 256MB 256MB 256MB 測試點數? 10 10 10 每個測試點分值 10 10 10 是否有 Special Judge ? ? ? 題?類型 傳統型 傳統型 傳統型 是否有附加?件 否 否 否 C++ 語??件名后綴 cpp cpp cpp C 語??件名后綴 c c c Pascal 語??件名后綴 pas pas pas 編譯開關 對于 C++ 語? -lm 對于 C 語? -lm 全部題?使??件輸?輸出，評測環境 Cena。 考試時間 3.5h。 忘了什么時候開始 到清晨才能?睡 也忘了什么叫做結尾 又有誰在乎呢 凌晨三點的窗前 播放著那段時光 有?個驕傲的少年 隱藏他的青春 — 張希/曹?《認真地老去》 2 監聽 monitor.in/.out/.cpp 弱小和?知不是?存的障礙，拖延癥才是。 【背景】 不閱讀本題的【背景】并不影響通過本題。 三體信息中沒有包含對三體??物形態的任何描述，?類要在四百多年 以后才能真正看到三體?。在閱讀信息時，葉?潔只能把三體?想象成?類 的形象。 1379 號監聽站已經存在了上千年，像這樣的監聽站，在三體世界中有 ?千個，它們全神貫注地聆聽著宇宙間可能存在的智慧?明的信息。 最初監聽站中有上百名監聽員，但隨著技術的進步，現在只有?個?值 守了。監聽員是?個卑微的職業，他們雖然?處恒溫且能保證?活供給的監 聽室中，在亂世紀不必脫?，但他們的?命也就在這??的空間中流逝，能 夠享受到的恒紀元快樂?其他?要少得多。 1379 號監聽員投過??的床?看著外?的三體世界，這是亂紀元的? 夜，巨?還沒有升起來，?多數?都處于脫?的冬眠中，甚?植物也本能地 脫?了，成了附著于地表沒有?命的?束?纖維。星光下，?地看上去像? ?塊冰冷的?屬。 這是最孤寂的時刻，在靜靜的午夜，宇宙向它的聆聽者展?著?漠的荒 涼。1379 號監聽員最不愿意看的，就是顯?器上緩緩移動的那條曲線，那是 監聽系統接收到的宇宙電波的波形，?意義的噪聲。他感到這條?限長的線 就是宇宙的抽象，?頭連著?限的過去，另?頭連著?限的未來，中間只有 為?規律??命的隨機起伏。?個個?低錯落的波峰就像?粒粒??不等的 沙?，整條線就像是所有沙粒排成?形成的?維沙漠，荒涼寂寥，長得令? ?法忍受。你可以沿著它向前向后??限遠，但永遠找不到歸宿。 【問題描述】 監聽的宇宙電波可以抽象成?個長度為 L 的?寫字母組成的字符串。 3 同時在三體?總結出來了 n 段敏感電波的樣?，每段敏感電波的長度 都是 m。 現在請你實現?個程序，求出在這長度為 L 的?寫字母組成的字符串 中某個敏感電波第?次出現的位置（位置從 1 開始計數） 。 如果從頭到尾，沒有任何敏感電波出現，輸出”no”（不帶雙引號） 。 【輸入格式】 第??三個整數 L, n, m。 接下來 n ?，每??個長度為 m 的字符串，表?敏感電波。 接下來??，?個長度為 L 的字符串，表?監聽到的電波。 【輸出格式】 輸出?個整數或者?個字符串”no”（不帶雙引號） 。 【樣例輸入 1】 11 3 3 aba cba abc aaabbabcaba 【樣例輸出 1】 6 【樣例輸入 2】 11 3 3 aba cba abc 4 aaabbabzabz 【樣例輸出 2】 no 【數據規模及約定】 對于前 30% 的數據，1 ≤ L ≤ 100, 1 ≤ n ≤ 100, 1 ≤ m ≤ 20。 對于前 50% 的數據，1 ≤ L ≤ 10000, 1 ≤ n ≤ 1000, 1 ≤ m ≤ 20。 對于另外 20% 的數據，n = 1。 對于前 100% 的數據，1 ≤ L ≤ 10 5 , 1 ≤ n ≤ 10 4 , 1 ≤ m ≤ 20。 5 實驗室 lab.in/.out/.cpp 光錐之內都是新聞。 【背景】 不閱讀本題的【背景】并不影響通過本題。 《時間之外的往事》(節選) 彎曲空間的動? 這個宇宙的空間并不是平坦的，?是存在著曲率，如果把宇宙的整體想 象為?張?膜，這張膜的表?是弧形的，整張膜甚?可能是?個封閉的肥皂 泡。雖然膜的局部看似平?，但空間曲率還是?處不在。 早在公元世紀，曾出現過許多極富野?的宇宙航?設想，其中之?就是 空間折疊。設想把?范圍空間的曲率?限增?，像?張紙?樣對折，把“紙 ?”上相距千萬光年的遙遠的兩點貼在?起。這個?案嚴格說來不應稱為宇 宙航?，?應該叫做。 “宇宙拖曳” ，因為它實質上并不是航?到?的地，?是 通過改變空間曲率把?的地花過來。 這種?吞宇宙的事只有上帝才做得?來. 如果加上基本理論的限制. 可能上帝也不?。 對于利?空間曲率航?，后來又出現了?個更溫和更局部的設想，?艘 處于太空中的飛船，如果能夠?某種?式把它后?的?部分空間熨平，減? 其曲率、那么飛船就會被前?曲率史?的空間拉過去，這就是曲率驅動。 曲率驅動不可能像空間折疊那樣瞬間到達?的地，但卻有可能使飛船以 ?限接近光速的速度航?。 但直到云天明情報被正確解讀前，曲率驅動仍是?個幻想，同上百個光 速飛?的幻想?案?樣， ?論從理論上還是技術上， 沒有?知道它是否可?。 【問題描述】 沿著著曲率驅動的思路，R 君開發出了時間旅?傳送門。 R 君將 n-1 個時間旅?傳送門部署到了 n 個星球。如果只?這 n-1 個 時間旅?傳送門，R 君發現這 n 個星球是兩兩可達的（也就是?棵樹） 。 6 但是時間旅?傳送門除了傳送的功能外還額外有著時間旅?的功能，? 如說 (X i , Y i , T i ) 這個傳送門，通過這個傳送門從 X i 到 Y i 時間就會增加 T i (T i 可正可負)，通過這個傳送門從 Y i 到 X i 時間就會減少 T i (T i 可正可 負)。 現在 R 君關?的問題是從 x 星球能不能通往 y 星球，同時時間恰好增 加 z（z 可正可負） 。 由于現在是?個樹形的結構，所以實際上兩點之間的路徑唯?，所以 R 君很快寫了個程序計算出了這個結果。 但是隨著 R 君繼續部署傳送門，這個問題變得復雜了起來，所以請你 來幫幫忙。 【輸入格式】 第??兩個整數 n，q。q 表?之后處理的事件的數量。 接下來 n-1 ?，每?三個整數 x i ,y i ,T i 。 接下來 q ?，每?四個正整數 k, x, y, t。 若 k=0，表?部署?個新的傳送門 (x,y,t)。 若 k=1，表?詢問是否可以從 x 到 y，使得時間恰好增加 t。 【輸出格式】 對于每個 k=1 的詢問，輸出???個答案 yes/no。 （?寫） 【樣例輸入】 5 5 1 2 1 2 3 1 3 4 1 4 5 2 1 1 5 5 1 2 5 5 1 1 5 10 7 0 2 4 -3 1 1 5 10 【樣例輸出】 yes no no yes 【樣例解釋】 添加 (2,4,-3) 后可以從 1->2->3->4->2->3->4->5， 時間變化是 1+1+1- (-3)+1+1+2=10。 【數據規模及約定】 對于前 30% 的數據，1 ≤ n ≤ 1000, 1 ≤ q ≤ 1000 , |T i | ≤ 10 9 。 對于另外 20% 的數據，不存在 k=0 的輸?。 對于另外 20% 的數據，只存在?條 k=0 的輸?。 對于前 100% 的數據，1 ≤ n ≤ 10 5 , 1 ≤ q ≤ 4 × 10 5 , |T i | ≤ 10 9 。 8 文明 civilization.in/.out/.cpp 給歲月以?明，?不是給?明以歲月。 【背景】 不閱讀本題的【背景】并不影響通過本題。 羅輯那邊的?星升了起來并來回移動，顯然是他站起?來踱步，在地球 上是可以的，但在宇宙中不?，下?我們引??個重要概念：猜疑鏈。挺怪 的詞?。我開始僅得到這么?個詞，她沒有解釋，但我后來終于從字?上推 測出了它的含義。他？他是誰？后?再說吧，我們繼續：如果你認為我是善 意的，這并不是你感到安全的理由，因為按照第?條公理，善意?明并不能 預先把別的?明也想成善意的，所以，你現在還不知道我是怎么認為你的， 你不知道我認為你是善意還是惡意；進?步，即使你知道我把你也想象成善 意的，我也知道你把我想象成善意的，但是我不知道你是怎么想我怎么想你 怎么想我的，挺繞的是不是？這才是第三層，這個邏輯可以?直向前延伸， 沒完沒了。我懂你的意思。這就是猜疑鏈。這種東西在地球上是見不到的。 ?類共同的物種、相近的?化、同處?個相互依存的?態圈、近在咫尺的距 離，在這樣的環境下，猜疑鏈只能延伸??兩層就會被交流所消解。但在太 空中，猜疑鏈則可能延伸得很長，在被交流所消解之前，?暗戰役那樣的事 已經發?了。 【問題描述】 R 君在繼續著宇宙社會學的研究，R 君發現是否為善意的?明與他們的 距離到本?明的距離的奇偶有很?的關系。 所以 R 君提出了如下簡化的問題，考慮?個 n 個節點帶邊權的樹，兩 點間距離是兩點間樹上路徑的邊權和。 R 君想知道對于?個點來說，到這個點是距離奇數的節點的距離和，與 到這個點距離是偶數的節點的距離和。 9 【輸入格式】 第??包含兩個整數 n, q。q 表?詢問數量。 接下來 n-1 ?，每?三個數字 (x,y,z) 表? x 與 y 之間的距離是 z。 接下來 q ?，每??個整數 x，表?詢問的節點為 x。 【輸出格式】 輸出包含 q ?，每?兩個整數，分別表?距離為奇數的節點的距離和與 距離為偶數的節點的距離和。 【樣例輸入】 4 4 1 2 1 2 3 2 2 4 3 1 2 3 4 【樣例輸出】 4 4 4 2 8 2 8 4 【樣例解釋】 每個點到 1 號點的距離：0,1,3,4 每個點到 2 號點的距離：1,0,2,3 每個點到 3 號點的距離：3,2,0,5 10 每個點到 4 號點的距離：4,3,5,0 【數據規模和約定】 對于前 20% 的數據，1 ≤ n ≤ 100。 對于前 40% 的數據，1 ≤ n ≤ 2000。 對于前 70% 的數據，1 ≤ n ≤ 5 × 10 4 。 對于前 100% 的數據，1 ≤ n ≤ 10 5 , q ≤ n, 1 ≤ z ≤ 10 3 。 11 （完） 12 題面

?

/* string + map 水過 */ #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<map>#define N 100007using namespace std; int n,m,l,ans,cnt; string s[10002]; map<string,bool>vis; string ss;int main() {freopen("monitor.in","r",stdin);freopen("monitor.out","w",stdout);scanf("%d%d%d",&l,&n,&m);for(int i=1;i<=n;i++)cin>>s[i],vis[s[i]]=1;cin>>s[0];for(int i=0;i<=l-m;i++){ss=s[0].substr(i,m);if(vis[ss]){ans=i+1;break;}}if(!ans) printf("no\n");else printf("%d\n",ans);fclose(stdin);fclose(stdout);return 0; }

?

?

/* 各種情況分析，由于路徑權值的相反性 只要有環，要么不走，要么等效完整走整數遍。 假設有k個環，每個環的邊權和為xi，那么問題轉化為 不定方程a*x1+b*x2+c*x3+....+m*xk=T是否存在整數解。 根據不定方程整數解的條件可知，gcd(x1~xm) | T 時有，否則無。 */ #include<bits/stdc++.h>#define N 411111 #define ll long longusing namespace std; int n,q; ll sum[N]; int toedge[N],cnt; struct Edge {int to,val,next; }; Edge edge[N<<1];int read() {int ret=0,neg=1;char c=getchar();while (c<'0' || c>'9'){if (c=='-') neg=-1;c=getchar();}while (c>='0' && c<='9'){ret=ret*10+c-'0';c=getchar();}return ret*neg; }ll SUM(int x,int y){return sum[y]-sum[x];} ll Abs(ll x){return x>0 ? x : -x;} ll gcd(ll x,ll y){return (y==0) ? x : gcd(y,x%y);}void add(int from,int to,int val) {edge[++cnt]=(Edge){to,val,toedge[from]};toedge[from]=cnt; }void dfs(int x,int fa) {for (int i=toedge[x]; i; i=edge[i].next){int to=edge[i].to;if (to==fa) continue;sum[to]=sum[x]+edge[i].val;dfs(to,x);} }int main() {freopen("lab.in","r",stdin);freopen("lab.out","w",stdout);n=read();q=read();int x,y,z;for (int i=1; i<n; i++){x=read();y=read();z=read();add(x,y,z);add(y,x,-z);}dfs(1,0);int k,t;ll xun=-1;for (int i=1; i<=q; i++){k=read();x=read();y=read();t=read();if (k==0){ll tmp=SUM(y,x);if (xun==-1) xun=Abs(tmp+t);else if (tmp+t!=0) xun=gcd(xun,Abs(tmp+t));}else{ll tmp=Abs((ll)t-SUM(x,y));if (xun==-1)if (tmp==0) puts("yes");else puts("no");else if (tmp%xun==0) puts("yes");else puts("no");}} }

?

?

#include<iostream> #include<cstdio> #include<cstring>#define N 100007 #define ll long longusing namespace std; ll n,m,ans1,ans2,cnt,tot; ll x,y,z,q; ll head[N],deep[N],sum[N],f[N][26]; ll in[N],F[N][2],son[N][2]; struct edge{ll u,v,w,nxt; }e[N<<1];inline ll read() {ll x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; }inline void add(int u,int v,int w) {e[++cnt].v=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt; }void dfs(int now,int fa,int c) {f[now][0]=fa;deep[now]=c;for(int i=head[now];i;i=e[i].nxt){int v=e[i].v;if(v==fa) continue;sum[v]=sum[now]+e[i].w;dfs(v,now,c+1);} }void get() {for(int j=1;j<=25;j++) for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1]; }int lca(int a,int b) {if(deep[a]<deep[b]) swap(a,b);int t=deep[a]-deep[b];for(int i=0;i<=t;i++) if(t&(1<<i)) a=f[a][i];if(a==b) return a;for(int i=25;i>=0;i--)if(f[a][i]!=f[b][i])a=f[a][i],b=f[b][i];return f[a][0]; }void solve1() {dfs(1,1,0);get();for(int i=1;i<=m;i++){tot=ans1=ans2=0;q=read();for(int j=1;j<=n;j++){if(j==q) continue;int res=lca(q,j);tot=sum[q]+sum[j]-2*sum[res];if(tot%2) ans1+=tot;else ans2+=tot;}cout<<ans1<<" "<<ans2<<endl;} }void dp(int u,int from)//0 偶數 {son[u][0]=son[u][1]=0;for(int i=head[u];i;i=e[i].nxt){int v=e[i].v;if(v==from) continue;dp(v,u);if(e[i].w%2==1){son[v][1]++;if(in[v]==1){son[v][1]++;son[u][1]++;F[u][0]+=e[i].w*son[v][0];F[u][1]+=e[i].w*son[v][1]; }else{son[u][1]+=son[v][0],son[u][0]+=son[v][1];F[u][0]+=F[v][1]+e[i].w*son[v][1];F[u][1]+=F[v][0]+e[i].w*son[v][0];F[u][1]+=e[i].w; }}else{son[v][0]++;if(in[v]==1){son[v][0]++;son[u][0]++;F[u][0]+=e[i].w*son[v][0];F[u][1]+=e[i].w*son[v][1]; }else{son[u][0]+=son[v][0],son[u][1]+=son[v][0];F[u][0]+=F[v][0]+e[i].w*son[v][0];F[u][1]+=F[v][1]+e[i].w*son[v][1]; F[u][0]+=e[i].w; }}} }void solve2() {for(int i=1;i<=m;i++){q=read();memset(f,0,sizeof F);memset(son,0,sizeof son);dp(q,q);cout<<F[q][1]<<" "<<F[q][0]<<endl;} }int main() {freopen("civilization.in","r",stdin);freopen("civilization.out","w",stdout);n=read();m=read();for(int i=1;i<n;i++){x=read();y=read();z=read();add(x,y,z);add(y,x,z);}if(n<=5000) solve1();else solve2();fclose(stdin);fclose(stdout);return 0; } 40暴力

?

#include <cstdio> #include <cstring> #include <algorithm>using namespace std;// 70%保證答案不爆intint n,q; int H[100005], X[200005], P[200005], w[200005], tot;inline void add(int x,int y,int z) {P[++tot]=y;X[tot]=H[x];H[x]=tot;w[tot]=z; } typedef long long LL; LL f[2][100005]; // 子樹 LL ans[2][100005]; int siz[2][100005]; // 子樹 int siz2[2][100005]; // 整棵樹void dfs1(int x,int fa) {siz[0][x] = 1;for(int i=H[x]; i; i=X[i]){if(P[i] == fa) continue;dfs1(P[i],x);if(w[i]&1){siz[0][x] += siz[1][P[i]];siz[1][x] += siz[0][P[i]];f[0][x] += f[1][P[i]] + w[i]*siz[1][P[i]];f[1][x] += f[0][P[i]] + w[i]*siz[0][P[i]];}else{siz[0][x] += siz[0][P[i]];siz[1][x] += siz[1][P[i]];f[0][x] += f[0][P[i]] + w[i]*siz[0][P[i]];f[1][x] += f[1][P[i]] + w[i]*siz[1][P[i]];}} }void dfs2(int x,int fa) {for(int i=H[x]; i; i=X[i]){if(P[i]==fa) continue;if(w[i]&1){siz2[0][P[i]] = siz2[1][x];siz2[1][P[i]] = siz2[0][x];ans[0][P[i]] = f[0][P[i]] + ans[1][x] - (f[0][P[i]]+w[i]*siz[0][P[i]]) + w[i]*(siz2[1][x]-siz[0][P[i]]) ;ans[1][P[i]] = f[1][P[i]] + ans[0][x] - (f[1][P[i]]+w[i]*siz[1][P[i]]) + w[i]*(siz2[0][x]-siz[1][P[i]]) ;}else{siz2[0][P[i]] = siz2[0][x];siz2[1][P[i]] = siz2[1][x];ans[0][P[i]] = f[0][P[i]] + ans[0][x] - (f[0][P[i]]+w[i]*siz[0][P[i]]) + w[i]*(siz2[0][x]-siz[0][P[i]]) ;ans[1][P[i]] = f[1][P[i]] + ans[1][x] - (f[1][P[i]]+w[i]*siz[1][P[i]]) + w[i]*(siz2[1][x]-siz[1][P[i]]) ;}dfs2(P[i],x);} }int main() {freopen("civilization.in", "r", stdin);freopen("civilization.out", "w", stdout);scanf("%d%d",&n,&q);for(int i=1,x,y,z; i<n; i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}dfs1(1,0);ans[0][1] = f[0][1];ans[1][1] = f[1][1];siz2[0][1] = siz[0][1];siz2[1][1] = siz[1][1];dfs2(1,0);int x;while(q--){scanf("%d",&x);printf("%lld %lld\n",ans[1][x],ans[0][x]);}fclose(stdout);return 0; } 正解待補檔

?

轉載于:https://www.cnblogs.com/L-Memory/p/9846404.html

總結

以上是生活随笔為你收集整理的清北刷题10.23night的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。