NOIP练习赛题目5
生活随笔
收集整理的這篇文章主要介紹了
NOIP练习赛题目5
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
?
| 小象涂色 |
| 難度級別：C； 運行時間限制：1000ms； 運行空間限制：262144KB； 代碼長度限制：2000000B |
| 試題描述 |
| 小象喜歡為箱子涂色。小象現在有c種顏色，編號為0~c-1；還有n個箱子，編號為1~n，最開始每個箱子的顏色為1。小象涂色時喜歡遵循靈感：它將箱子按編號排成一排，每次涂色時，它隨機選擇[L，R]這個區間里的一些箱子（不選看做選0個），為之涂上隨機一種顏色。若一個顏色為a的箱子被涂上b色，那么這個箱子的顏色會變成（a*b）modc。請問在k次涂色后，所有箱子顏色的編號和期望為多少？ |
| 輸入 |
| 第一行為T，表示有T組測試數據。 對于每組數據，第一行為三個整數n,c,k。 接下來k行，每行兩個整數Li，Ri，表示第i個操作的L和R。 |
| 輸出 |
| 對于每組測試數據，輸出所有箱子顏色編號和的期望值，結果保留9位小數。 |
| 輸入示例 |
| 3 3?2?2 2?2 1?3 1?3?1 1?1 5?2?2 3?4 2?4 |
| 輸出示例 |
| 2.062500000 1.000000000 3.875000000 |
| 其他說明 |
| 數據范圍： 40%的數據1?<=?T?<=?5，1?<=?n,?k?<=?15，2?<=?c?<=?20 100%的數據滿足1?<=?T?<=?10，1?<=?n,?k?<=?50，2?<=?c?<=?100，1?<=?Li?<=?Ri?<=?n |
首先，操作順序是沒有影響的，那么我們可以記錄每個位置進行了多少次操作。
就可以寫個DP，得出每個位置進行若干次操作后的期望顏色。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } double f[55][105]; int n,c,k,cnt[55]; int main() {dwn(T,read(),1) {n=read();c=read();k=read(); memset(f,0,sizeof(f));memset(cnt,0,sizeof(cnt));f[0][1]=1;rep(t,0,k-1) rep(j,0,c-1) {f[t+1][j]+=f[t][j]*0.5;rep(k,0,c-1) f[t+1][(j*k)%c]+=f[t][j]*(0.5/c); }double ans=0; rep(i,1,k) {int l=read(),r=read();rep(j,l,r) cnt[j]++; }rep(i,1,n) rep(j,0,c-1) ans+=f[cnt[i]][j]*j;printf("%.9lf\n",ans);}return 0; } View Code?
| 行動！行動！ |
| 難度級別：C； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| 大CX國的大兵Jack接到一項任務：敵方占領了n座城市（編號0~n-1），有些城市之間有雙向道路相連。Jack需要空降在一個城市S，并徒步沿那些道路移動到T城市。雖然Jack每從一個城市到另一個城市都會受傷流血，但大CX國畢竟有著“過硬”的軍事實力，它不僅已經算出Jack在每條道路上會損失的血量，還給Jack提供了k個“簡易急救包”，一個包可以讓Jack在一條路上的流血量為0。Jack想知道自己最少會流多少血，不過他畢竟是無腦的大兵，需要你的幫助。 |
| 輸入 |
| 第一行有三個整數n,m,k，分別表示城市數，道路數和急救包個數。 第二行有兩個整數，S,T。分別表示Jack空降到的城市編號和最終要到的城市。 接下來有m行，每行三個整數a,b,c，表示城市a與城市b之間有一條雙向道路。 |
| 輸出 |
| Jack最少要流的血量。 |
| 輸入示例 |
| 5?6?1 0?3 3?4?5 0?1?5 0?2?100 1?2?5 2?4?5 2?4?3 |
| 輸出示例 |
| 8 |
| 其他說明 |
| 數據范圍： 對于30%的數據,2<=n<=50,1<=m<=300,k=0; 對于50%的數據,2<=n<=600,1<=m<=6000,0<=k<=1; 對于100%的數據,2<=n<=10000,1<=m<=50000,0<=k<=10. |
拆點最短路。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } const int maxn=10010; const int maxm=200010; struct HeapNode {int u,d;bool operator < (const HeapNode& ths) const {return d>ths.d;} }; int n,m,k,s,t,first[maxn],next[maxm]; int to[maxm],dis[maxm],d[15][maxn],done[maxn*12]; priority_queue<HeapNode> Q; void spfa() {rep(i,0,k) rep(j,0,n-1) d[i][j]=1<<30;Q.push((HeapNode){s+n*k,0});d[k][s]=0;while(!Q.empty()) {if(done[Q.top().u]) {Q.pop();continue;}else done[Q.top().u]=1;int x=Q.top().u%n,k2=Q.top().u/n;Q.pop();ren {if(d[k2][to[i]]>d[k2][x]+dis[i]) {d[k2][to[i]]=d[k2][x]+dis[i];Q.push((HeapNode){to[i]+n*k2,d[k2][to[i]]}); }if(d[k2-1][to[i]]>d[k2][x]) {d[k2-1][to[i]]=d[k2][x];Q.push((HeapNode){to[i]+n*k2-n,d[k2-1][to[i]]}); }}} } int main() {n=read();m=read();k=read();s=read();t=read();rep(i,1,m) {int x=read();to[i]=read();to[i+m]=x;dis[i+m]=dis[i]=read();next[i]=first[x];first[x]=i;next[i+m]=first[to[i]];first[to[i]]=i+m; }spfa();int ans=1<<30;rep(i,0,k) ans=min(ans,d[i][t]);printf("%d\n",ans);return 0; } View Code?
| Hzwer的隕石 |
| 難度級別：C； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| 經過不懈的努力，Hzwer召喚了很多隕石。已知Hzwer的地圖上共有n個區域，且一開始的時候第i個隕石掉在了第i個區域。有電力噴射背包的ndsf很自豪，他認為搬隕石很容易，所以他將一些區域的隕石全搬到了另外一些區域。 在ndsf愉快的搬運過程中，Hzwer想知道一些隕石的信息。對于Hzwer詢問的每個隕石i，你必須告訴他，在當前這個時候，i號隕石在所在區域x、x區域共有的隕石數y、以及i號隕石被搬運的次數z。 ? |
| 輸入 |
| 輸入的第一行是一個正整數T。表示有多少組輸入數據。 接下來共有T組數據，對于每組數據，第一行包含兩個整數：N和Q。 接下來Q行，每行表示一次搬運或一次詢問，格式如下： T?A?B：表示搬運，即將所有在A號球所在地區的隕石都搬到B號球所在地區去。 Q?A：悟空想知道Ａ號隕石的x，y，z |
| 輸出 |
| 對于第ｉ組數據，第一行輸出“Case?i：”接下來輸出每一個詢問操作的x，y，z，每一個詢問操作的答案占一行。每組數據之間沒有空行。 |
| 輸入示例 |
| 2 3?3 T?1?2 T?3?2 Q?2 3?4 T?1?2 Q?1 T?1?3 Q?1 |
| 輸出示例 |
| Case?1: 2?3?0 Case?2: 2?2?1 3?3?2 |
| 其他說明 |
| 數據范圍： 20%的數據保證：0≤T≤20，2＜N＜＝100，2＜Q＜＝100。 100%的數據保證：0≤T≤100，2＜N＜＝10000，2＜Q＜＝10000。 對于所有數據保證搬運操作中AB在Ｎ的范圍內且所在區域不相同。： |
前兩問很好做，寫個并查集就行了。第三問可以這么做：如果x區域的隕石全部搬到y區域，那么將x->y的值+1，則x地區的隕石被搬運的次數就是x到根節點的距離，并查集記錄一下信息就行了。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } const int maxn=10010; int pa[maxn],s[maxn],d[maxn]; int findset(int x) {if(pa[x]==x) return x;int res=findset(pa[x]);d[x]+=d[pa[x]];return pa[x]=res; } int main() {int T=read();rep(Case,1,T) {printf("Case %d:\n",Case);int n=read(),m=read();rep(i,1,n) pa[i]=i,s[i]=1,d[i]=0;rep(i,1,m) {char cmd[12];scanf("%s",cmd);if(cmd[0]=='Q') {int y,x=findset(y=read());printf("%d %d %d\n",x,s[x],d[y]);}else {int x=findset(read()),y=findset(read());pa[x]=y;s[y]+=s[x];d[x]++;}}}return 0; } View Code?
| 挖掘機 |
| 難度級別：C； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| 今天，喪尸czy開著挖掘機去上學(……)。但是他發現他的mz滿天下，所以一路上他碰到了好多他的mz。一開始他以1km/min的速度(=60km/h……)開著挖掘機前進。他發現他只會在恰好到達某一時刻或者到達某個距離遇到mz。每次遇到mz，czy都會毫不猶豫的把她們順路捎走(^_^)。但是他實在是太虛了，以至于當有i個mz時他的速度下降到1/(i+1)。具體說，一開始czy以1km/min速度前進，有1個mz的時候速度變為1/2 km/min，有2個時變為1/3 km/min……以此類推。現在問題來了，給出每個mz在何時出現，請你算出czy到學校要多久。 |
| 輸入 |
| 輸入第一行2個數n，m，分別表示mz數和czy與學校的距離(km) 接下來2到n+1行由字符串與數字構成 Dist??x表示在距離達到x?km時出現一個mz Time??x表示在時間達到x?min時出現一個mz |
| 輸出 |
| 輸出一個整數，表示到達學校的時間。如果不能整除，直接輸出整數部分即可。 |
| 輸入示例 |
| 2?20 Time?3 Dist?10 |
| 輸出示例 |
| 47 |
| 其他說明 |
| 數據范圍 對于30%數據，n,m<=50 對于50%數據，n,m<=2000 對于100%數據，n,m<=200000,x<=10^9,保證輸入的數字都是整數 |
奇怪的題目，排序亂搞。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } typedef long long ll; const int maxn=200010; int A[maxn],B[maxn],n1,n2; char s[20]; int main() {int n=read(),m=read();rep(i,1,n) {scanf("%s",s);if(s[0]=='T') A[++n1]=read();else B[++n2]=read();}B[++n2]=m;sort(A+1,A+n1+1);sort(B+1,B+n2+1);double ans=0,p=0.0;int c=1,cur=1;rep(i,1,n2) {while(cur<=n1&&ans+c*(B[i]-p)>A[cur]) {p+=(A[cur]-ans)/c;ans=A[cur];c++;cur++;}ans+=c*(B[i]-p);p=B[i];c++;}printf("%lld\n",(ll)ans);return 0; } View Code?
| 藏寶圖 |
| 難度級別：C； 運行時間限制：4000ms； 運行空間限制：262144KB； 代碼長度限制：2000000B |
| 試題描述 |
| Czy發現了一張奇怪的藏寶圖。圖上有n個點，m條無向邊。已經標出了圖中兩兩之間距離dist。但是czy知道，只有當圖剛好又是一顆樹的時候，這張藏寶圖才是真的。如果藏寶圖是真的，那么經過點x的邊的邊權平均數最大的那個x是藏著寶物的地方。請計算這是不是真的藏寶圖，如果是真的藏寶之處在哪里。 |
| 輸入 |
| 輸入數據第一行一個數T,表示T組數據。 對于每組數據，第一行一個n，表示藏寶圖上的點的個數。 接下來n行,每行n個數，表示兩兩節點之間的距離。 |
| 輸出 |
| 輸出一行或兩行。第一行”Yes”或”No”，表示這是不是真的藏寶圖。 若是真的藏寶圖，第二行再輸出一個數，表示哪個點是藏寶之處。 |
| 輸入示例 |
| 2 3 0?7?9 7?0?2 9?2?0 3 0?2?7 2?0?9 7?9?0 |
| 輸出示例 |
| Yes 1 Yes 3 樣例解釋:第一棵樹的形狀是1--2--3。1、2之間的邊權是7，2、3之間是2。 ?第二棵樹的形狀是2--1--3。2、1之間的邊權是2，1、3之間是7。 |
| 其他說明 |
| 數據范圍 對于30%數據，n<=50,1<=樹上的邊的長度<=10^9。 對于50%數據，n<=600. 對于100%數據，1<=n<=2500 0<=dist[i][j]<=10^12,T<=5 |
如果一個圖是樹，則整個圖的最小生成樹為這個圖。
可以計算出原圖的最小生成樹，重建整個圖，再重判是否有矛盾即可。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i;i=next[i]) using namespace std; typedef long long ll; inline ll read() {ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } const int maxn=2510; struct Edge {int u,v;ll w;bool operator < (const Edge& ths) const {return w<ths.w;} }E[maxn*maxn/2]; ll d[maxn][maxn]; int n,pa[maxn],first[maxn],next[maxn<<1],to[maxn<<1],dis[maxn<<1],e; int findset(int x) {return x==pa[x]?x:pa[x]=findset(pa[x]);} void AddEdge(int u,int v,int w) {to[++e]=v;dis[e]=w;next[e]=first[u];first[u]=e;to[++e]=u;dis[e]=w;next[e]=first[v];first[v]=e; } int vis[maxn]; ll dist[maxn]; queue<int> Q; void bfs(int x) {memset(vis,0,sizeof(vis));Q.push(x);vis[x]=1;dist[x]=0;while(!Q.empty()) {x=Q.front();Q.pop();ren if(!vis[to[i]]) {vis[to[i]]=1;dist[to[i]]=dist[x]+dis[i];Q.push(to[i]);}} } int main() {dwn(T,read(),1) {n=read();int m=0;e=0;memset(first,0,sizeof(first));rep(i,1,n) rep(j,1,n) d[i][j]=read();rep(i,1,n) {pa[i]=i;int best=0;rep(j,1,n) if(i<j) E[++m]=(Edge){i,j,d[i][j]};}sort(E+1,E+m+1);rep(i,1,m) {int x=findset(E[i].u),y=findset(E[i].v);if(x!=y) pa[x]=y,AddEdge(E[i].u,E[i].v,E[i].w);}int ok=1;rep(i,1,n) {bfs(i);rep(j,1,n) if(d[i][j]!=dist[j]) ok=0;}if(!ok) puts("No");else {puts("Yes");if(n==1) puts("1");else {int ans=0;double mx=0.0;rep(x,1,n) {int cnt=0;double val=0;ren cnt++,val+=dis[i];val/=cnt;if(val>mx) mx=val,ans=x;}printf("%d\n",ans);}}}return 0; } View Code?
| 最大公約數 |
| 難度級別：C； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| 話說CD比較欠扁，他表示在課室的日子沒有教主在旁邊打他的日子太寂寞了，所以這一晚，他終于來到了電腦室被打。由于CD是大家的寵物，于是大家都來打CD了。電腦室里有n個人，第i個人希望打CD ai下。但是太多人打CD，他又會不爽，于是他規定只能有K個人打到他，并且為了公平起見，最終K個人打他的次數都必須是相同的，CD規定這個次數就是這K個人希望打他的次數的最大公約數。為什么是最大公約數呢？因為他覺得被打的次數是GCD的話他才會變成Glad CD。之前說了，CD比較欠扁，于是CD希望，K個人打他的次數的和最大。你能告訴他他最后總共會被打多少下么？ |
| 輸入 |
| 第一行兩個正整數n，k。 第二行n個正整數，表示每個人希望打CD多少下。 |
| 輸出 |
| 輸出一個正整數表示CD會被打多少下 |
| 輸入示例 |
| 3?1 1?2?3 |
| 輸出示例 |
| 3 |
| 其他說明 |
| 數據說明 對于30%的數據，保證k≤n≤20。 對于50%的數據，保證輸入中所有數小于5000。 對于100%的數據，保證輸入中所有數小于500000，k≤n。 |
枚舉答案ans，數一數有多少數是ans的倍數。根據調和數列定理，時間復雜度為O(nlogn)
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } const int maxn=500010; int S[maxn],ans; int main() {int n=read(),k=read();rep(i,1,n) S[read()]++;rep(i,1,500000) {int cnt=0;for(int j=i;j<=500000;j+=i) cnt+=S[j];if(cnt>=k) ans=max(ans,i);}printf("%lld\n",(long long)ans*k);return 0; } View Code?
| 密碼 |
| 難度級別：C； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| 哪里有壓迫，哪里就有反抗。 ??? moreD的寵物在法庭的幫助下終于反抗了。作為一只聰明的寵物，他打算把魔法使moreD的魔法書盜去，奪取moreD的魔法能力。但moreD怎么會讓自己的魔法書輕易地被盜取？moreD在魔法書上設置了一個密碼鎖，密碼鎖上有一個問題。 ??? 施以斯臥鋪魔法吧，你有M次機會，如此將得完美密碼。 ??? 然后是一串小寫字母串。 ??? moreD的寵物斯臥鋪魔法就是施法時的字符串其中相鄰兩位交換。 ??? 而moreD對于完美密碼的定義自然是最小字典序了。 ??? 請幫助moreD的寵物，想出密碼吧。 |
| 輸入 |
| 第一行一個整數M，表示操作次數。 第二行一串小寫字母組成的字符串S，如題目所示。 |
| 輸出 |
| 輸出完美密碼 |
| 輸入示例 |
| 3 dcba |
| 輸出示例 |
| adcb |
| 其他說明 |
| 【數據范圍】 對于30%的數據|S|≤10? 對于60%的數據|S|≤3,000 對于100%的數據8≤|S|≤100,000?M≤(|S|-8)^2+2 【后記】 寵物最終戰勝了moreD,和自己的寵物快樂地生活著。 【樣例解釋】 先對第3，4兩位施法，字符串變成dcab，然后對第2，3兩位施法，字符串變成dacb，最后對第1，2兩位施法，字符串變成adcb。 |
按位貪心，考慮將字符c換到該位置是否可行。注意每次移動[l,r]區間的同時會讓[l,r]中的所有字符向左移一位，可以用個數據結構來維護單點修改區間和。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; typedef long long ll; const int maxn=100010; char s[maxn]; int n,c[maxn],first[maxn],next[maxn]; ll m; void add(int x,int v) {for(;x<=n;x+=x&-x) c[x]+=v; } int sum(int x) {int res=0;for(;x;x-=x&-x) res+=c[x];return res; } int main() {scanf("%lld%s",&m,s+1);n=strlen(s+1);dwn(i,n,1) next[i]=first[s[i]-'a'],first[s[i]-'a']=i,add(i,1);rep(i,1,n) {int j=0,tmp;for(;j<=25;j++) if(first[j]&&(tmp=sum(first[j]-1))<=m) {m-=tmp;add(first[j],-1);first[j]=next[first[j]];break;}putchar(j+'a');}return 0; } View Code?
| 取數 |
| 難度級別：C； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| 有一個取數的游戲。初始時，給出一個環，環上的每條邊上都有一個非負整數。這些整數中至少有一個0。然后，將一枚硬幣放在環上的一個節點上。兩個玩家就是以這個放硬幣的節點為起點開始這個游戲，兩人輪流取數，取數的規則如下： ??? （1）選擇硬幣左邊或者右邊的一條邊，并且邊上的數非0； ??? （2）將這條邊上的數減至任意一個非負整數(至少要有所減小)； ??? （3）將硬幣移至邊的另一端。 ??? 如果輪到一個玩家走，這時硬幣左右兩邊的邊上的數值都是0，那么這個玩家就輸了。 如下圖，描述的是Alice和Bob兩人的對弈過程，其中黑色節點表示硬幣所在節點。結果圖(d)中，輪到Bob走時，硬幣兩邊的邊上都是0，所以Alcie獲勝。 ? 現在，你的任務就是根據給出的環、邊上的數值以及起點（硬幣所在位置），判斷先走方是否有必勝的策略。 |
| 輸入 |
| 第一行一個整數N（N≤20），表示環上的節點數。 第二行N個數，數值不超過30，依次表示N條邊上的數值。硬幣的起始位置在第一條邊與最后一條邊之間的節點上。 |
| 輸出 |
| 僅一行。若存在必勝策略，則輸出“YES”，否則輸出“NO”。 |
| 輸入示例 |
| 樣例輸入1 4 2?5?3?0 樣例輸入2 3 0?0?0 |
| 輸出示例 |
| 樣例輸入1 YES 樣例輸入2 NO |
。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } int A[25],n; int main() {n=read();rep(i,1,n) A[i]=read();int r=n,l=0;while(A[r]) r--;while(A[l+1]) l++;r=n-r;if(l&1||r&1) puts("YES");else puts("NO");return 0; } View Code?
| 游戲 |
| 難度級別：C； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| windy學會了一種游戲。? 如：? ??? 1 2 3 4 5 6? 2 3 1 5 4 6? 3 1 2 4 5 6? 1 2 3 5 4 6? 2 3 1 4 5 6? 3 1 2 5 4 6? 1 2 3 4 5 6? 這時，我們就有若干排1到N的排列，上例中有7排。? 現在windy想知道，對于所有可能的對應關系，有多少種可能的排數。 |
| 輸入 |
| 輸入文件game.in包含一個整數，N。 |
| 輸出 |
| 輸出文件game.out包含一個整數，可能的排數。 |
| 輸入示例 |
| 【輸入樣例一】 3 【輸入樣例二】 10 |
| 輸出示例 |
| 【輸出樣例一】 3 【輸出樣例二】 16 |
| 其他說明 |
| 數據規模和約定 30%的數據，滿足?1?<=?N?<=?10?。? 100%的數據，滿足?1?<=?N?<=?1000?。 |
將每個置換分解成循環的形式，則操作數為循環長度的LCM。
那么問題轉化成將N拆成若干正整數的和，問LCM有幾種。
考慮唯一分解定理，打出1到N素數表，設f[i][j]表示用了前i個素數目前和為j的可能數，轉移就很簡單了。
最后答案=∑f[cnt][i]|1<=i<=N。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } typedef long long ll; const int maxn=1010; int vis[maxn],p[maxn],n,cnt; ll ans,f[170][maxn]; void init() {rep(i,2,n) if(!vis[i]) {p[++cnt]=i;for(int j=i*i;j<=n;j+=i) vis[j]=1;} } int main() {n=read();init();f[0][0]=1;rep(i,1,cnt) {rep(j,0,n) f[i][j]=f[i-1][j];for(int j=p[i];j<=n;j*=p[i]) rep(k,0,n-j) f[i][j+k]+=f[i-1][k];}rep(i,0,n) ans+=f[cnt][i];printf("%lld\n",ans);return 0; } View Code?
| 迎接儀式 |
| 難度級別：C； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| LHX教主要來X市指導OI學習工作了。為了迎接教主，在一條道路旁，一群Orz教主er穿著文化衫站在道路兩旁迎接教主，每件文化衫上都印著大字。一旁的Orzer依次擺出“歡迎歡迎歡迎歡迎……”的大字，但是領隊突然發現，另一旁穿著“教”和“主”字文化衫的Orzer卻不太和諧。 為了簡單描述這個不和諧的隊列，我們用“j”替代“教”，“z”替代“主”。而一個“j”與“z”組成的序列則可以描述當前的隊列。為了讓教主看得盡量舒服，你必須調整隊列，使得“jz”子串盡量多。每次調整你可以交換任意位置上的兩個人，也就是序列中任意位置上的兩個字母。而因為教主馬上就來了，時間僅夠最多作K次調整（當然可以調整不滿K次），所以這個問題交給了你。 |
| 輸入 |
| 輸入文件welcome.in的第1行包含2個正整數N與K，表示了序列長度與最多交換次數。 第2行包含了一個長度為N的字符串，字符串僅由字母“j”與字母“z”組成，描述了這個序列。 |
| 輸出 |
| 輸出文件welcome.out僅包括一個非負整數，為調整最多K次后最后最多能出現多少個“jz”子串。 |
| 輸入示例 |
| 5?2 zzzjj |
| 輸出示例 |
| 2 |
| 其他說明 |
| 【樣例說明】 第1次交換位置1上的z和位置4上的j，變為jzzzj； 第2次交換位置4上的z和位置5上的j，變為jzzjz。 最后的串有2個“jz”子串。 【數據規模】 對于10%的數據，有N≤10； 對于30%的數據，有K≤10； 對于40%的數據，有N≤50； 對于100%的數據，有N≤500，K≤100 |
這道題想法很巧妙。將交換操作認為是兩步操作：1、將j變成z。2、將z變成j。
設f[i][j][k]表示[1,i]，進行了j次操作1，k次操作2最多的jz數。
1.f[i][j][k]=f[i-1][j][k];
2.f[i][j][k]=f[i-2][j-(A[i-1]=='j')][k-(A[i]=='z')]+1
只有當操作1和操作2數量相同時才認為是合法操作。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } const int maxn=510; const int maxk=110; char s[maxn]; int f[maxn][maxk][maxk],ans; int main() {int n=read(),m=read();scanf("%s",s+1);rep(i,2,n) rep(x,0,m) rep(y,0,m) {f[i][x][y]=f[i-1][x][y];int t1=s[i-1]=='z',t2=s[i]=='j';if(x>=t1&&y>=t2) f[i][x][y]=max(f[i][x][y],f[i-2][x-t1][y-t2]+1);if(x==y) ans=max(ans,f[i][x][y]);}int cnt1=0,cnt2=0;rep(i,1,n) cnt1+=s[i]=='j',cnt2+=s[i]=='z';printf("%d\n",min(ans,min(cnt1,cnt2)));return 0; } View Code?
| 連連看 |
| 難度級別：C； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| 有時大型游戲玩膩味了，小Z也會玩玩弱智級的小游戲，比如連連看。但小Z眼力不行，常常得分很低。于是，他找到了你，希望你能幫他找出一種獲勝方案。 連連看的游戲規則很簡單：玩家可以將 2 個相同圖案的牌連接起來，連接線不多于 3 條線段，就可以成功將兩個牌消除。將游戲界面上的牌全部消除掉，玩家就勝利了。 |
| 輸入 |
| 輸入文件card.in的第一行為兩個正整數m和n，表示連連看游戲的矩陣大小。 接下來的m行，每行n個英文大寫字母（為了計算方便，只用A~E五個字母），表示牌的種類，相同字母表示同種牌。 |
| 輸出 |
| 輸出文件card.out。 若能獲勝，則輸出共一行，包括m×n/2個英文大寫字母，第i個字母表示第i次消除的牌的種類。若有多解，輸出字典順序最小的解。 若不能獲勝，則輸出共一行，包括字符串“Game?over.”。 |
| 輸入示例 |
| 輸入樣例1 2?1 A A 輸入樣例2 2?1 A B |
| 輸出示例 |
| 輸出樣例1 A 輸出樣例2 Game?over. |
| 其他說明 |
| 限制： 100%的數據滿足：m×n<=12 |
超級無敵大暴力。。。
調了2h+。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } char Map[13][13]; const int mx[]={1,-1,0,0}; const int my[]={0,0,-1,1}; int n,m,vis[13][13][5][4]; string ans; int dfs2(int x,int y,int x1,int y1,int dir,int t) {if(vis[x][y][dir][t]) return 0;vis[x][y][dir][t]=1;if(t>2) return 0;if(x==x1&&y==y1) return 1;int nx=x+mx[dir],ny=y+my[dir];if(nx>=0&&ny>=0&&nx<=n+1&&ny<=m+1&&!Map[nx][ny]) if(dfs2(nx,ny,x1,y1,dir,t)) return 1;rep(ndir,0,3) if(dfs2(x,y,x1,y1,ndir,t+1)) return 1;return 0; } int check(int x1,int y1,int x2,int y2) {rep(dir,0,3) {memset(vis,0,sizeof(vis));if(dfs2(x1,y1,x2,y2,dir,0)) return 1;}return 0; } void dfs(int cur,int final,string cd) {if(cur==final) ans=min(ans,cd);else {rep(x,1,n) rep(y,1,m) rep(nx,1,n) rep(ny,1,m) if(Map[x][y]&&Map[nx][ny]&&Map[x][y]==Map[nx][ny]) {if(x==nx&&ny==y) continue;char c=Map[nx][ny];Map[nx][ny]=Map[x][y]=0;if(check(x,y,nx,ny)) dfs(cur+1,final,cd+c);Map[nx][ny]=Map[x][y]=c;}} } int main() {n=read();m=read();if(n*m&1) puts("Game over.");else {rep(i,1,n) scanf("%s",Map[i]+1);rep(j,0,m+1) Map[0][j]=Map[n+1][j]=0;rep(j,0,n+1) Map[j][0]=Map[j][m+1]=0;ans="ZZZZZZZ";dfs(0,n*m/2,"");if(ans=="ZZZZZZZ") puts("Game over.");else cout<<ans<<endl;}return 0; } View Code?
| LazyChild黑OJ |
| 難度級別：C； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| LazyChild開了一家“善良OJ”。但大多數人都不知道，這其實是家黑OJ。親愛的同學，請不要驚訝，古時候有黑店，現代為什么不能有黑OJ呢？每AC一道題，網站便會自動在電腦上安裝一種木馬。LazyChild通過竊取信息獲取收益（如網游帳號、OI資料、YuanY和TT的照片等等）。 作為一名資深黑客，老Z某日突然發現，“善良OJ”上的木馬，自己電腦上都沒有。這可十分讓他過意不去。老Z決定通過多A題，來豐富自己電腦的病毒庫。 經過調查，老Z發現，很多木馬是不能共存的。比如“和諧”木馬與“團結”木馬，兩者只能任選其一。然而，老Z是個完美主義者，他想要自己的病毒庫盡可能充實。 老Z不懈的追求最終感動了上天。天上的神仙（半仙？）“牛人雨”給這個問題稍稍降低了一點難度。神仙規定，對于n種木馬，有且僅有(n-1)對不能共存，并且對于每種木馬，都存在至少一個木馬與之不能共存。 老Z不在乎自己AC多少題。請告訴他，他最多能從“善良OJ”上獲取木馬的個數。 |
| 輸入 |
| 第一行，一個正整數n，表示木馬個數。 剩余(n-1)行，每行一對木馬，表示他們不能共存。（保證相同的木馬可以共存，任意不同兩行的描述不等價） 木馬編號從0至(n-1) |
| 輸出 |
| 一行，老Z最多獲得木馬的個數。你可以認為開始時沒有任何木馬。 |
| 輸入示例 |
| 3 0?1 1?2 |
| 輸出示例 |
| 2 |
| 其他說明 |
| 【數據規模】 對于100％的數據，1<=n<=200 |
樹上獨立集。寫個樹上DP或匹配算法都行。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } const int maxn=210; int first[maxn],next[maxn<<1],to[maxn<<1],e; void AddEdge(int u,int v) {to[++e]=v;next[e]=first[u];first[u]=e;to[++e]=u;next[e]=first[v];first[v]=e; } int f[maxn][2]; int dp(int x,int tp,int fa) {int& ans=f[x][tp];if(ans>=0) return ans;ans=0;if(!tp) {int v1=0,v2=0;ren if(to[i]!=fa) {v1+=dp(to[i],0,x);v2+=dp(to[i],1,x);}ans=max(v1,v2+1);}else ren if(to[i]!=fa) ans+=dp(to[i],0,x);return ans; } int main() {memset(f,-1,sizeof(f));int n=read();rep(i,2,n) AddEdge(read()+1,read()+1);printf("%d\n",dp(1,0,-1));return 0; } View Code?
| 機房人民大團結 |
| 難度級別：C； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| 最近，機房出了一個不團結分子：Dr.Weissman。他經常欺騙同學們吃一種“教授糖豆”，使同學們神志不清，毆打他人，砸爛計算機，破壞機房團結。幸運地，一個和諧家認清了Dr.Weissman的本質。機房人民團結在一起，共同對抗Dr.Weissman及“教授糖豆”。 同學們十分具有社會責任感：他們害怕“教授糖豆”流向社會，導致動亂。于是，剛才提到的和諧家身先士卒，為了實驗，品嘗“教授糖豆”。 每個“教授糖豆”的性質都有所不同。同志們已經研究出每個糖豆對人的影響。具體地，每個糖豆都有一個破壞值，吃掉這顆糖豆后，身先士卒的和諧家會對機房造成一定的破壞，破壞程度為先前累積的破壞值加上本次食用糖豆的破壞值，而且這顆“教授糖豆”的破壞值會加入累積。為了減小實驗造成的破壞，同學們準備了幾顆“治療糖豆“，功能是無條件將累積的“破壞值”清零。 由于實驗要求，和諧家只能按照給定的順序吃掉“教授糖豆”，但可以隨時吃掉一顆或多顆“治療糖豆”。 你能幫助和諧家同志盡量減小實驗所造成的破壞嗎？ |
| 輸入 |
| 第一行，兩個數，用空格，分隔開，一個n，一個m。（n，m均為正整數。）n表示“教授糖豆”的數目，m表示“治療糖豆”的數目。 剩余n行，每行1個正整數，表示“教授糖豆”的破壞值。和諧家必須按照給定的順序，一次一個，吃掉所有“教授糖豆”。 |
| 輸出 |
| 一行，一個數，表示實驗造成的最小破壞。 |
| 輸入示例 |
| 3?1 1?2?3 |
| 輸出示例 |
| 7 |
| 其他說明 |
| 【數據規模】 對于100%的數據，1<=n<=100，m<=n 所有破壞值的加和小于10^9。 |
設f[i][j]表示已經吃了前i個“教授糖豆”，已用了j個“治療糖豆”的最小破壞。
隨便優化優化就行了。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } typedef long long ll; const int maxn=110; int n,m,A[maxn]; ll f[maxn][maxn],g[maxn][maxn]; int main() {n=read();m=read()+1;rep(i,1,n) A[i]=read();rep(l,1,n) {ll val=0;rep(r,l,n) val+=A[r],g[l][r]=g[l][r-1]+val;}rep(i,1,n) f[0][i]=1ll<<60;rep(i,1,n) {f[i][1]=g[1][i];rep(j,2,i) {f[i][j]=1ll<<60;rep(k,j-1,i-1) f[i][j]=min(f[i][j],f[k][j-1]+g[k+1][i]);}rep(j,i+1,n) f[i][j]=1ll<<60;}printf("%lld\n",f[n][m]);return 0; } View Code?
| 四輪車 |
| 難度級別：A； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| 在地圖上散落著n個車輪，小J想用它們造一輛車。要求如下： 1. 一輛車需要四個車輪，且四個車輪構成一個正方形 2.車輪不能移動 ? 你需要計算有多少種造車的方案（兩個方案不同當且僅當所用車輪不全相同，坐標相同的兩個車輪視為不同車輪）。 |
| 輸入 |
| 第一行一個整數n 接下來n行，每行兩個整數x?y，表示在(x,y)處有一個車輪 |
| 輸出 |
| 一行一個整數，表示方案數 |
| 輸入示例 |
| 9 0?0 1?0 2?0 0?2 1?2 2?2 0?1 1?1 2?1 |
| 輸出示例 |
| 6 |
| 其他說明 |
| 【數據范圍】 30%的數據保證n≤30? 100%的數據保證1≤n≤1000;|x|,|y|<20000 |
這道題BJWC出過，不過范圍是1<=N<=50000。
至于1<=N<=1000，直接枚舉兩角用個hash判其余兩點就行了。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[p];i;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } const int maxn=1010; const int HASH=937; struct Hash_Map {int x[maxn],y[maxn],cnt[maxn],next[maxn],n;int first[HASH];void init() {memset(first,0,sizeof(first));memset(cnt,0,sizeof(cnt));n=0;}void insert(int X,int Y) {int p=(X*Y)%HASH;if(p<0) p+=HASH;ren if(x[i]==X&&y[i]==Y) {cnt[i]++;return;}x[++n]=X;y[n]=Y;cnt[n]=1;next[n]=first[p];first[p]=n;}int query(int X,int Y) {int p=(X*Y)%HASH;if(p<0) p+=HASH;ren if(x[i]==X&&y[i]==Y) return cnt[i];return 0;} }S; int n,x[maxn],y[maxn]; int solve() {S.init();int res=0;rep(i,1,n) S.insert(x[i],y[i]);rep(i,1,n) rep(j,i+1,n) if(x[i]==x[j]) {int gap=abs(y[i]-y[j]);res+=S.query(x[i]-gap,y[i])*S.query(x[i]-gap,y[j]);}return res; } int main() {n=read();rep(i,1,n) x[i]=read(),y[i]=read();int ans=solve();rep(i,1,n) {int a=x[i],b=y[i];x[i]=a+b;y[i]=a-b;}printf("%d\n",ans+solve());return 0; } View Code?
| 盤子序列 |
| 難度級別：A； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| 有n個盤子。盤子被生產出來后，被按照某種順序摞在一起。初始盤堆中如果一個盤子比所有它上面的盤子都大，那么它是安全的，否則它是危險的。稱初始盤堆為A，另外有一個開始為空的盤堆B。為了掩蓋失誤，生產商會對盤子序列做一些“處理”，每次進行以下操作中的一個：(1)將A最上面的盤子放到B最上面；(2)將B最上面的盤子給你。在得到所有n個盤子之后，你需要判斷初始盤堆里是否有危險的盤子。 |
| 輸入 |
| 輸入文件包含多組數據（不超過10組） 每組數據的第一行為一個整數n 接下來n個整數，第i個整數表示你收到的第i個盤子的大小 |
| 輸出 |
| 對于每組數據，如果存在危險的盤子，輸出”J”，否則輸出”Y” |
| 輸入示例 |
| 3 2?1?3 3 3?1?2 |
| 輸出示例 |
| Y J |
| 其他說明 |
| 【數據范圍】 20%的數據保證n<=8 80%的數據保證n<=1,000 100%的數據保證1<=n<=100,000，0<盤子大小<1,000,000,000且互不相等 |
離散后用個stack判判就行了。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } const int maxn=100010; int n,top,A[maxn],T[maxn],S[maxn]; int main() {while(scanf("%d",&n)==1) {rep(i,1,n) T[i]=A[i]=read();sort(T+1,T+n+1);rep(i,1,n) A[i]=lower_bound(T+1,T+n+1,A[i])-T;int cur=1;top=0;rep(i,1,n) {S[++top]=i;while(top&&S[top]==A[cur]&&cur<=n) top--,cur++;}puts(top?"J":"Y");}return 0; } View Code?
| 點名 |
| 難度級別：A； 運行時間限制：3000ms； 運行空間限制：262144KB； 代碼長度限制：2000000B |
| 試題描述 |
| 在J班的體育課上，同學們常常會遲到幾分鐘，但體育老師的點名卻一直很準時。老師只關心同學的身高，他會依次詢問當前最矮的身高，次矮的身高，第三矮的身高，等等。在詢問的過程中，會不時地有人插進隊伍里。你需要回答老師每次的詢問。 |
| 輸入 |
| 第一行兩個整數n?m，表示先后有n個人進隊，老師詢問了m次 第二行n個整數，第i個數Ai表示第i個進入隊伍的同學的身高為Ai 第三行m個整數，第j個數Bj表示老師在第Bj個同學進入隊伍后有一次詢問 |
| 輸出 |
| m行，每行一個整數，依次表示老師每次詢問的答案。數據保證合法 |
| 輸入示例 |
| 7?4 9?7?2?8?14?1?8 1?2?6?6 |
| 輸出示例 |
| 9 9 7 8 |
| 其他說明 |
| 【樣例解釋】 (9){No.1?=?9};?(9?7){No.2?=?9};?(9?7?2?8?14?1){No.3?=?7;?No.4?=?8} 【數據范圍】 40%的數據保證n≤1000? 100%的數據保證1≤m≤n≤30000;0≤Ai<2^32 |
Treap練習。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; typedef long long ll; inline ll read() {ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } const int maxn=60010; struct Node {Node* ch[2];int r,s;ll v;void maintain() {s=ch[0]->s+ch[1]->s+1;} }nodes[maxn],*null=&nodes[0]; int ToT; Node* newnode(ll v) {Node* o=&nodes[++ToT];o->v=v;o->ch[0]=o->ch[1]=null;o->s=1;o->r=rand();return o; } void rotate(Node* &o,int d) {Node* k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;o->maintain();k->maintain();o=k; } void insert(Node* &o,ll v) {if(o==null) o=newnode(v);else {int d=v>o->v;insert(o->ch[d],v);if(o->ch[d]->r>o->r) rotate(o,d^1);else o->maintain();} } ll query(Node* &o,ll k) {if(k>o->s) return -1;if(o->ch[0]->s+1==k) return o->v;if(o->ch[0]->s>=k) return query(o->ch[0],k);return query(o->ch[1],k-o->ch[0]->s-1); } void print(Node* &o) {if(o==null) return;print(o->ch[0]);printf("%d ",o->v);print(o->ch[1]); } Node *root=null; struct Operation {int type,time,id;ll v;bool operator < (const Operation& ths) const {if(time!=ths.time) return time<ths.time;return type<ths.type;} }Q[maxn]; ll n,m,ans[maxn]; int main() {n=read();m=read();rep(i,1,n) Q[i]=(Operation){0,i,0,read()};rep(i,1,m) Q[i+n]=(Operation){1,read(),i,i};n+=m;sort(Q+1,Q+n+1);rep(i,1,n) {if(!Q[i].type) insert(root,Q[i].v);else ans[Q[i].id]=query(root,Q[i].v);}rep(i,1,m) printf("%lld\n",ans[i]);return 0; } View Code?
| 序列問題 |
| 難度級別：A； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B |
| 試題描述 |
| 小H 是個善于思考的學生，她正在思考一個有關序列的問題。 她的面前浮現出了一個長度為n 的序列{ai}，她想找出兩個非空的集合S、T。 這兩個集合要滿足以下的條件： 1. 兩個集合中的元素都為整數，且都在[1, n] 里，即Si，Ti ∈[1, n]。 2. 對于集合S 中任意一個元素x，集合T 中任意一個元素y，滿足x < y。 3. 對于大小分別為p, q 的集合S 與T，滿足 a[s1] xor a[s2] xor a[s3] ... xor a[sp] = a[t1] and a[t2]and a[t3] ... and a[tq]. 小H 想知道一共有多少對這樣的集合(S,T)，你能幫助她嗎？ |
| 輸入 |
| 第一行，一個整數n 第二行，n?個整數，代表ai。 |
| 輸出 |
| 僅一行，表示最后的答案，保證答案在long?long范圍內。 |
| 輸入示例 |
| 4 1?2?3?3 |
| 輸出示例 |
| 4 |
| 其他說明 |
| 【樣例解釋】 S?=?{1,2},?T?=?{3}，?1?^?2?=?3?=?3?(^為異或) S?=?{1,2},?T?=?{4},?1?^?2?=?3?=?3 S?=?{1,2}，?T?=?{3，4}?1?^?2?=?3?&?3?=?3?（&為與運算） S?=?{3}，?T?=?{4}?3?=?3?=?3 【數據范圍】 30%:?1?<=?n?<=?10 60%:?1?<=?n?<=?100 100%:?1?<=?n?<=?1000,?0?<=?ai?<?1024 |
因為對于集合S 中任意一個元素x，集合T 中任意一個元素y，滿足x < y。
所以問題其實是將序列分為前后兩半，且前一半選出一些數的異或值=后一半選出一些數的且值。
以前一半的異或值為例：
設f[i][j][0]表示前i個數，異或和為j，且選了最后一個數的方案數。
設f[i][j][1]表示前i個數，異或和為j，且沒選最后一個數的方案數。
轉移很簡單。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<bitset> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f; } typedef long long ll; const int maxn=1010; const int maxv=1030; int n,A[maxn]; ll ans,f[maxn][maxv][2],g[maxn][maxv][2]; int main() {n=read();rep(i,1,n) A[i]=read();rep(i,1,n) {f[i][A[i]][1]++;rep(j,0,1023) {f[i][j^A[i]][1]+=(f[i-1][j][0]+f[i-1][j][1]);f[i][j][0]+=(f[i-1][j][0]+f[i-1][j][1]);}}dwn(i,n,1) {g[i][A[i]][1]++;rep(j,0,1023) {g[i][j&A[i]][1]+=(g[i+1][j][0]+g[i+1][j][1]);g[i][j][0]+=(g[i+1][j][0]+g[i+1][j][1]);}}rep(i,1,n-1) rep(j,0,1023) ans+=(f[i][j][0]+f[i][j][1])*g[i+1][j][1];printf("%lld\n",ans);return 0; } View Code?
轉載于:https://www.cnblogs.com/wzj-is-a-juruo/p/4939410.html
總結
以上是生活随笔為你收集整理的NOIP练习赛题目5的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python读xml文件
- 下一篇： 「机械」4大传动方式优劣对比：机械、电气