?

選舉

---

?

?

題目描述

C國的總統選舉委員會最近遇到了一些麻煩。

他們在統計各省對H先生的支持率（百分比）時，把支持率四舍五入到了整數。等他們公布結果后，該國媒體發現這些省份的支持率之和不等于100（百分比）！在媒體黑幕聲的質疑下，他們不得不找你尋求幫助。

你將得到各省四舍五入后的支持率，請計算這些省份的支持率在四舍五入前的和是否可能等于100？支持率是以百分比的形式統計的。

請注意，各省的支持率可以是一個包含任意多位的有限小數。一個小數在四舍五入到整數時，若小數點后第一位小于5則舍，大于等于5則入。

例如：

26、17、58是一種可能的支持率，因為它們可能是25.8、16.5、57.7四舍五入后得到的，而25.8+16.5+57.7=100。

49、49是一種不可能的支持率，因為當9的個數有限時，無論有多少個9，均有49.499…99+49.499…99<100。

輸入格式

輸入包含多組數據，第一行是一個整數T，表示數據組數。

接下來是T組數據，每組數據的第一行是一個整數N，表示參與選舉的省份個數。第二行是N個整數，表示各省四舍五入后的支持率。

輸出格式

對于每組數據，若是一種可能的支持率，輸出Yes，否則輸出No。

樣例輸入

2

2

49 49

3????

26 17 58

樣例輸出

No

Yes

數據范圍與約定

對于30%的數據，1<=n<=3；

對于50%的數據，1<=n<=5；

對于80%的數據，1<=四舍五入后各省的支持率<=99；

對于100%的數據，1<=n<=10000，輸入數據中的所有整數均在有符號16位整數范圍內。

#include<cstdio> using namespace std; #define O(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout); #define ct register int #define f(c) for(ct i=1;i<=c;i++) typedef long long ll; int read(){ct f=1,x=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;for(;'0'<=c&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);return x*f;} int main(){O("election");double total;bool out=0;int w;int t=read();while(t--){int n=read(),x;w=n;f(n){x=read(),total+=x,x==0?w--:w=w;if(x<0)out=1;}if(out){printf("No\n");continue;}if(total>100)total-w*0.5<=100?printf("Yes\n"):printf("No\n");elseif(total<100)total+n*0.49999999999>=100?printf("Yes\n"):printf("No\n");else printf("Yes\n");total=0;}return 0; }

入門題沒什么好講了吧。（雖然我之前的程序因為沉迷三目WA了一個點）

?

異象石

---

?

題目描述

Adera是Microsoft應用商店中的一款解謎游戲。

異象石是進入Adera中異時空的引導物，在Adera的異時空中有一張地圖。這張地圖上有N個點，有N-1條雙向邊把它們連通起來。起初地圖上沒有任何異象石，在接下來的M個時刻中，每個時刻會發生以下三種類型的事件之一：

地圖的某個點上出現了異象石（已經出現的不會再次出現）；

地圖某個點上的異象石被摧毀（不會摧毀沒有異象石的點）；

向玩家詢問使所有異象石所在的點連通的邊集的總長度最小是多少。

請你作為玩家回答這些問題。

輸入格式

第一行有一個整數N，表示點的個數。

接下來N-1行每行三個整數x,y,z，表示點x和y之間有一條長度為z的雙向邊。

第N+1行有一個正整數M。

接下來M行每行是一個事件，事件是以下三種格式之一：

+ x??? 表示點x上出現了異象石

- x表示點x上的異象石被摧毀

?表示詢問使當前所有異象石所在的點連通所需的邊集的總長度最小是多少。

輸出格式

對于每個 ?事件，輸出一個整數表示答案。

樣例輸入

6

1 2 1

1 3 5

4 1 7

4 5 3

6 4 2

10

+ 3

+ 1

?

+ 6

?

+ 5

?

- 6

- 3

?

樣例輸出

5

14

17

10

數據范圍與約定

對于30%的數據，1?≤?n, m?≤?1000。

對于另20%的數據，地圖是一條鏈，或者一朵菊花。

對于100%的數據，1?≤?n, m?≤?10^5, 1?≤?x, y?≤?n, x?≠?y, 1?≤?z?≤?10^9。

?

#include<cstdio> #include<set> #define MN 100000 #define MD 17 using namespace std; #define O(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout); #define ct register int #define f(i,c) for(ct i=1;i<=c;i++) #define I set<int>::iterator #define ll long long int read(){ct f=1,x=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;for(;'0'<=c&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);return x*f;} char st[5];set<int> s; int n,m,head[MN+5],cnt=0,fa[MD+1][MN+5],dfn[MN+5],p[MN+5],D[MN+5],dn=0; long long ans=0,dep[MN+5]; struct edge{int to,next,w;}e[MN*2+5]; inline void ins(int f,int t,int w){e[++cnt]=(edge){t,head[f],w};head[f]=cnt;e[++cnt]=(edge){f,head[t],w};head[t]=cnt; } void Pre(int x,int f){dfn[x]=++dn;p[dn]=x;fa[0][x]=f;for(int i=head[x];i;i=e[i].next)if(e[i].to!=f) D[e[i].to]=D[x]+1,dep[e[i].to]=dep[x]+e[i].w,Pre(e[i].to,x);} int lca(int x,int y){if(D[x]<D[y])swap(x,y);for(int k=D[x]-D[y],j=0;k;k>>=1,++j)if(k&1)x=fa[j][x];if(x==y)return x;for(int i=MD;~i;--i)if(fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];return fa[0][x];} long long dis(int x,int y){x=p[x];y=p[y];return dep[x]+dep[y]-2*dep[lca(x,y)];} int main(){O("stone");n=read();for(int i=1,j,k;i<n;++i) j=read(),k=read(),ins(j,k,read());Pre(1,0);f(i,MD)f(j,n)fa[i][j]=fa[i-1][fa[i-1][j]];m=read();for(int i=1,j=0;i<=m;++i){scanf("%s",st+1);if(st[1]=='?')printf("%lld\n",ans>>1);else if(st[1]=='+'){int x=dfn[read()];s.insert(x);if(++j==1) {ans=0;continue;}I it2,it=s.lower_bound(x);int pre,aft;it==s.begin()?pre=*--(it2=s.end()):pre=*--(it2=it);++(it2=it)==s.end()?aft=*s.begin():aft=*it2;ans+=dis(pre,x)+dis(x,aft)-dis(pre,aft);}else if(st[1]=='-'){int x=dfn[read()];if(--j<=1){ans=0;s.erase(s.find(x));continue;}I it=s.lower_bound(x),it2;int pre,aft;if(it==s.begin()) pre=*--(it2=s.end()); else pre=*--(it2=it);if(++(it2=it)==s.end()) aft=*s.begin();else aft=*it2;ans-=dis(pre,x)+dis(x,aft)-dis(pre,aft);s.erase(it);}}return 0;}

?

序列變換

---

?

?

題目描述

給定一個長度為N的數列Ai。

你可以對數列進行若干次操作，每次操作可以從數列中任選一個數，把它移動到數列的開頭或者結尾。

求最少經過多少次操作，可以把數列變成單調不減的。“單調不減”意味著數列中的任意一個數都不大于排在它后邊的數。

輸入格式

第一行是一個正整數N。

第二行是N個正整數Ai。

輸出格式

輸出一個整數，表示最少需要的操作次數。

樣例輸入

5

6 3 7 8 6

樣例輸出

2

數據范圍與約定

對于30%的數據，滿足1≤n≤10。

對于60% 的數據，滿足1≤n≤1000。

對于100% 的數據，滿足1≤n≤1000000，1≤Ai≤1000000。

?

#include<cstdio> #include<algorithm> #include<vector> #define O(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout); #define f(a,b,c,d) for(int a=b;a-d!=c;a+=d) using namespace std; int n,m,ans,l,r; int a[1000001],q[1000001]; vector<int> b[1000001]; int main(){O("change");scanf("%d",&n);f(i,1,n,1)scanf("%d",&a[i]),b[a[i]].push_back(i),m=max(m,a[i]);l=1;r=0;f(i,1,m,1){reverse(b[i].begin(), b[i].end());f(j,0,b[i].size()-1,1){int k=b[i][j];while(l<=r&&q[r]>k){while(l<r&&a[q[l]]<a[q[r]]) l++;r--;}ans=max(ans,r-l+2+j);}for(int j=b[i].size()-1;j>=0;j--)q[++r]=b[i][j];}printf("%d",n-ans);return 0;}

?

轉載于:https://www.cnblogs.com/muzu/p/7744363.html

總結

以上是生活随笔為你收集整理的10.27 afternoon similated match的全部內容，希望文章能夠幫你解決所遇到的問題。

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