10.27 afternoon similated match

选举

题目描述

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。

样例输入

49 49

26 17 58

样例输出

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
");continue;}
        if(total>100)total-w*0.5<=100?printf("Yes
"):printf("No
");
        else
        if(total<100)total+n*0.49999999999>=100?printf("Yes
"):printf("No
");
        else printf("Yes
");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上的异象石被摧毁

?表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。

输出格式

对于每个 ?事件，输出一个整数表示答案。

样例输入

1 2 1

1 3 5

4 1 7

4 5 3

6 4 2

+ 3

+ 1

+ 6

+ 5

- 6

- 3

样例输出

数据范围与约定

对于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
",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。

输出格式

输出一个整数，表示最少需要的操作次数。

样例输入

6 3 7 8 6

样例输出

数据范围与约定

对于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;}