第一次參加省賽，可能也是最后一次了。。有點遺憾，但是收獲還是很多的。濟南大學真大，飯菜也很好吃，志愿者小姐姐也很漂亮。上來題出的很快，差不多不到一個半小時就出了五道題，然后wa了兩發。后面三個半小時全程掛機，H和L題一直沒出，思路有問題。最后五題拿銅。遺憾收場。要是五題出的在快點就是銀牌了（畢竟是銅牌靠前，菜是原罪）
補題H和L。
H
Median

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4124
賽場上一直想拓撲排序，各種拓撲排序，然后想出各種不對的條件。一直wa，，，下了賽場才知道，不一定要是確定的，把所有不確定的找出來就行。啊啊啊。我們想一下，其實那個點可以作為中位數的條件就是大于或者小于這個數的個數都不大于n/2,就有可能作為中位數。其實就是正反各建一次邊，正著反著找出各個點的子樹（類似）節點數。邊找邊判斷就可以了。唉，難受的一批

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<map> #include<vector> #include<queue> using namespace std;const int maxx=1e2+10; int mp1[maxx][maxx]; int mp2[maxx][maxx]; int in[maxx]; int vis[maxx]; int n,m;void init() {memset(mp1,0,sizeof(mp1));memset(mp2,0,sizeof(mp2));memset(vis,0,sizeof(vis));memset(in,0,sizeof(in)); }int dfs1(int cur) {int ans=1;vis[cur]=1;for(int i=1;i<=n;i++){if(mp1[cur][i]&&vis[i]==0){vis[i]=1;ans+=dfs1(i);}}return ans; }int dfs2(int cur) {int ans=1;vis[cur]=1;for(int i=1;i<=n;i++){if(mp2[cur][i]&&vis[i]==0){vis[i]=1;ans+=dfs2(i);}}return ans; }int main() {int t;scanf("%d",&t);while(t--){ scanf("%d%d",&n,&m);init();//初始化！！！！int x,y;int flag1=1;for(int i=0;i<m;i++){scanf("%d%d",&x,&y);mp1[x][y]=1;mp2[y][x]=1;in[y]++;}queue<int> p;for(int i=1;i<=n;i++){if(in[i]==0){p.push(i); }}while(p.size())//判斷環，如果有環，肯定不對的。。{int x=p.front();p.pop();if(vis[x]) continue;vis[x]=1;for(int i=1;i<=n;i++){if(mp1[x][i]){in[i]--;if(in[i]==0){p.push(i);} }}}int flag=1;for(int i=1;i<=n;i++){if(vis[i]==0){flag=0;break;}}if(flag==0){for(int i=1;i<=n;i++) printf("0");printf("\n");continue;}for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));int x=dfs1(i)-1;//小于memset(vis,0,sizeof(vis));int y=dfs2(i)-1;//大于if(x>n/2||y>n/2) printf("0");else printf("1");}printf("\n");}return 0; } /*4321 10 8 1 2 2 5 4 6 3 7 8 9 2 9 3 4 5 8*/

L Tokens on the Segments

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4120
賽場上的時候看出是貪心來了，按著左端點，右端點，區間長度都排序來找，但是一直wa，后來隊友寫了一發暴力，還是wa，嚶嚶嚶。后來知道用優先隊列去貪心，想了想確實比單一的排一次序好得多。菜的想哭。。

#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<vector> #define ll long long using namespace std;const int maxx=1e5+100; struct node{ll l,r;node(ll a=0,ll b=0){l=a;r=b;}bool operator < (const node &a)const{if(l!=a.l) return l>a.l;else return r>a.r;} }; int n;int main() {int t;scanf("%d",&t);while(t--){scanf("%d",&n);ll l,r;priority_queue<node> p; for(int i=0;i<n;i++){scanf("%lld%lld",&l,&r);p.push(node(l,r));}ll maxn=-1;ll ans=0;while(!p.empty()){node a;a=p.top();p.pop();if(a.l<=maxn&&a.l+1<=a.r) {p.push(node(a.l+1,a.r));continue;}if(a.l>maxn){ans++;maxn=max(maxn,a.l);}}printf("%lld\n",ans);} }

后面還有藍橋和南昌邀請賽。愿不忘初心，方得始終。加油！！！
努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的山东省第十届ACM浪潮杯补题的全部內容，希望文章能夠幫你解決所遇到的問題。

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