10.18 模拟赛

被低年级大佬暴踩的一次比赛 AK失败获得#3

T1 括号

题目大意：

对于任意 i 位置若与 n-i+1 相反则输出YES 否则输出NO

思路：

暴力判断即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #define inf 2139062143
11 #define ll long long
12 #define MAXN 100100
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 char s[200];
22 int n,a[200];
23 inline int work()
24 {
25     for(int i=1;i<=n;i++)
26         if((a[i]^a[n-i+1])==0) return 0;
27     return 1;
28 }
29 int main()
30 {
31     freopen("brackets.in","r",stdin);
32     freopen("brackets.out","w",stdout);
33     int T=read();
34     while(T--)
35     {
36         scanf("%s",s+1);n=strlen(s+1);
37         for(int i=1;i<=n;i++)
38             if(s[i]=='(') a[i]=1;
39             else a[i]=0;
40         puts(work()?"Yes":"No");
41     }
42 }

View Code

T2 地球危机

题目大意：

一个三维数列每个点有点权每次操作对于一个子平行六面体减去一个值输出第几次操作后出现一个小于0的点

A*B*C,m<=1e6

思路：

想到经典问题noip借教室可以二分答案然后差分+前缀和维护操作复杂度 Om

查询时复杂度ABC 需要推一下差分

因为ABC 不定所以不能开三维数组需要hash 但写的时候hash错了而且数组开小了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #define inf 2139062143
11 #define ll long long
12 #define MAXN 5001000
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 int A,B,C,m,n,ok;
22 int val[MAXN];
23 ll sum[MAXN];
24 int al[MAXN],ar[MAXN],bl[MAXN],br[MAXN],cl[MAXN],cr[MAXN],x,w[MAXN],ans;
25 inline int calc(int i,int j,int k) {return i*C*B+j*C+k;}
26 struct P10
27 {
28     inline void work()
29     {
30         for(int t=1;t<=m;t++)
31         {
32             for(int i=al[t];i<=ar[t];i++)
33                 for(int j=bl[t];j<=br[t];j++)
34                     for(int k=cl[t];k<=cr[t];k++)
35                         {sum[calc(i,j,k)]-=w[t];if(sum[calc(i,j,k)]<0) {ok=1;break;}}
36             if(ok) {printf("%d
",t);return ;}
37         }
38     }
39 }p40;
40 int cheque()
41 {
42     for(int i=1;i<=A;i++)
43         for(int j=1;j<=B;j++)
44             for(int k=1;k<=C;k++)
45             {
46                 sum[calc(i,j,k)]+=sum[calc(i-1,j,k)]+sum[calc(i,j-1,k)]+sum[calc(i,j,k-1)]-sum[calc(i-1,j-1,k)]-sum[calc(i-1,j,k-1)]-sum[calc(i,j-1,k-1)]+sum[calc(i-1,j-1,k-1)];
47                 if(sum[calc(i,j,k)]+val[calc(i,j,k)]<0LL) return 1;
48             }
49     return 0;
50 }
51 int main()
52 {
53     freopen("attack.in","r",stdin);
54     freopen("attack.out","w",stdout);
55     A=read(),B=read(),C=read(),m=read();
56     for(int i=1;i<=A;i++)
57         for(int j=1;j<=B;j++)
58             for(int k=1;k<=C;k++) sum[calc(i,j,k)]=val[calc(i,j,k)]=read();
59     for(int t=1;t<=m;t++) 
60         al[t]=read(),ar[t]=read(),bl[t]=read(),br[t]=read(),cl[t]=read(),cr[t]=read(),w[t]=read();
61     if(A*B*C<=5000) {p40.work();return 0;}
62     int l=1,r=m,mid;
63     while(l<=r)
64     {
65         mid=l+r>>1;
66         memset(sum,0,sizeof(sum));
67         for(int t=1;t<=mid;t++)
68             sum[calc(al[t],bl[t],cl[t])]-=w[t],
69             sum[calc(al[t],bl[t],cr[t]+1)]+=w[t],
70             sum[calc(al[t],br[t]+1,cl[t])]+=w[t],
71             sum[calc(ar[t]+1,bl[t],cl[t])]+=w[t],
72             sum[calc(al[t],br[t]+1,cr[t]+1)]-=w[t],
73             sum[calc(ar[t]+1,br[t]+1,cl[t])]-=w[t],
74             sum[calc(ar[t]+1,bl[t],cr[t]+1)]-=w[t],
75             sum[calc(ar[t]+1,br[t]+1,cr[t]+1)]+=w[t];
76         if(cheque()) r=mid-1,ans=mid;
77         else l=mid+1;
78     }
79     printf("%d",ans);
80 }

View Code

T3 付账

题目大意：

n个人，每个人带了a[i]的钱，他们一共要付S块钱，求每个人付的钱的最小标准差

思路：

可以贪心

排序后从小到大枚举剩余的人是否可以负剩下的钱不可以这个人就可以付a[i] 的钱否则剩下的人皆为剩余S/剩余n

（精度挂了得了80分放上石神的标程）

 1 #include<algorithm>
 2 #include<cmath>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<ctime>
 7 #include<iomanip>
 8 #include<iostream>
 9 #include<map>
10 #include<queue>
11 #include<stack>
12 #include<vector>
13 #define rep(i,x,y) for(register int i=(x);i<=(y);i++)
14 #define dwn(i,x,y) for(register int i=(x);i>=(y);i--)
15 #define eps 1e-10
16 #define maxn 500010
17 using namespace std;
18 int read()
19 {
20     int x=0,f=1;char ch=getchar();
21     while(!isdigit(ch)&&ch!='-')ch=getchar();
22     if(ch=='-')f=-1,ch=getchar();
23     while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
24     return x*f;
25 }
26 void write(int x)
27 {
28     int f=0;char ch[20];
29     if(!x){putchar('0'),putchar('
');return;}
30     if(x<0)x=-x,putchar('-');
31     while(x)ch[++f]=x%10+'0',x/=10;
32     while(f)putchar(ch[f--]);
33     putchar('
');
34 }
35 long double now,avg,b[maxn],S,dn,ans;
36 int n;
37 int main()
38 {
39     freopen("eatout.in","r",stdin);
40     freopen("eatout.out","w",stdout);
41     scanf("%d%llf",&n,&S),dn=(double)n;
42     rep(i,1,n)scanf("%llf",&b[i]);
43     sort(b+1,b+n+1);avg=S/n;
44     rep(i,1,n)
45     {
46         long double di=(double)(i-1);
47         if(b[i]>avg)/*cout<<i<<" "<<(S-now)/(dn-di)<<endl,*/b[i]=((S-now)/(dn-di)>b[i])?b[i]:(S-now)/(dn-di);
48         now+=b[i];
49     }
50     rep(i,1,n)/*cout<<"i:"<<i<<" b:"<<b[i]<<endl,*/ans+=(b[i]-avg)*(b[i]-avg);
51     cout<<fixed<<setprecision(4)<<sqrt(ans/dn);
52     return 0;
53 }

View Code