csps模拟9495凉宫春日的忧郁，漫无止境的八月，简单计算，格式化，真相题解
分类:
IT文章
•
2025-01-23 07:53:37
题面：https://www.cnblogs.com/Juve/articles/11767239.html
94，95的T3都没改出来，是我太菜了。。。
凉宫春日的忧郁：
比较$x^y$和$y!$的大小，如果打高精会T掉
正解：把两个数取log，则$log_2x^y=ylog_2x$，$log_2y!=sumlimits_{i=1}^{y}log_2i$
然后就A了
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<cmath>
6 #define int long long
7 using namespace std;
8 int t,x,y;
9 signed main(){
10 freopen("yuuutsu.in","r",stdin);
11 freopen("yuuutsu.out","w",stdout);
12 scanf("%lld",&t);
13 while(t--){
14 scanf("%lld%lld",&x,&y);
15 long double xx=y*log2(x);
16 long double yy=0.0;
17 for(int i=1;i<=y;++i){
18 yy+=log2(i);
19 }
20 if(xx<=yy) puts("Yes");
21 else puts("No");
22 }
23 return 0;
24 }
View Code
漫无止境的八月：
如果满足的话必须保证所有%k同余的位置上的和一样，所以打个map就好了。。。
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<unordered_map>
6 using namespace std;
7 const int MAXN=2e6+5;
8 int read(){
9 int x=0,f=1;char ch=getchar();
10 while(ch<'0'||ch>'9'){
11 if(ch=='-') f=-1;
12 ch=getchar();
13 }
14 while(ch>='0'&&ch<='9'){
15 x=(x<<3)+(x<<1)+ch-'0';
16 ch=getchar();
17 }
18 return x*f;
19 }
20 int n,k,q,a[MAXN],sum[MAXN];
21 unordered_map<int,int>mp;
22 signed main(){
23 freopen("august.in","r",stdin);
24 freopen("august.out","w",stdout);
25 n=read(),k=read(),q=read();
26 for(int i=1;i<=n;++i){
27 a[i]=read();
28 sum[i%k]+=a[i];
29 }
30 for(int i=0;i<k;++i) ++mp[sum[i%k]];
31 if(mp[sum[0]]==k) puts("Yes");
32 else puts("No");
33 for(int i=1;i<=q;++i){
34 int pos=read(),val=read();
35 a[pos]+=val;
36 --mp[sum[pos%k]];
37 sum[pos%k]+=val;
38 ++mp[sum[pos%k]];
39 if(mp[sum[0]]==k) puts("Yes");
40 else puts("No");
41 }
42 return 0;
43 }
44 /*
45 5 2 5
46 1 1 1 2 1
47 3 −1
48 1 −1
49 3 1
50 3 1
51 1 −1
52 */
View Code
简单计算：
$2*sumlimits_{i=0}^{p}lfloorfrac{i*q}{p}
floor=sumlimits_{i=0}^{p}lfloorfrac{i*q}{p}
floor+lfloorfrac{(p-i)*q}{p}
floor$
所以原式=$(p+1)*q-sumlimits_{i=0}^{p}[(p|i*q)?0:1]=(p+1)*q-p+gcd(p,q)$
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #define int long long
6 using namespace std;
7 int t,p,q,ans;
8 int gcd(int a,int b){
9 return b==0?a:gcd(b,a%b);
10 }
11 signed main(){
12 freopen("simplecalc.in","r",stdin);
13 freopen("simplecalc.out","w",stdout);
14 scanf("%lld",&t);
15 while(t--){
16 scanf("%lld%lld",&p,&q);
17 ans=(p+1)*q-p+gcd(p,q);
18 printf("%lld
",ans>>1);
19 }
20 return 0;
21 }
View Code
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #define int long long
6 using namespace std;
7 const int MAXN=1e6+5;
8 int n,ans=0x3f3f3f3f3f3f3f3f,l,r;
9 struct node{
10 int pre,now,w;
11 friend bool operator < (node p,node q){
12 if(p.w>0&&q.w>0){
13 return p.pre<q.pre;
14 }
15 if(p.w<0&&q.w<0){
16 return p.now>q.now;
17 }
18 if(p.w==0&&q.w==0){
19 return p.pre>q.pre;
20 }
21 if(p.w==0){
22 return q.w<0;
23 }
24 if(q.w==0){
25 return p.w>0;
26 }
27 if(p.w>0&&q.w<0) return 1;
28 if(p.w<0&&q.w>0) return 0;
29 return 1;
30 }
31 }a[MAXN];
32 bool check(int val){
33 for(int i=1;i<=n;++i){
34 if(a[i].pre>val) return 0;
35 val-=a[i].pre,val+=a[i].now;
36 }
37 return 1;
38 }
39 signed main(){
40 freopen("reformat.in","r",stdin);
41 freopen("reformat.out","w",stdout);
42 scanf("%lld",&n);
43 for(int i=1;i<=n;++i){
44 scanf("%lld%lld",&a[i].pre,&a[i].now);
45 r+=a[i].pre;
46 a[i].w=a[i].now-a[i].pre;
47 }
48 sort(a+1,a+n+1);
49 while(l<r){
50 int mid=(l+r)>>1;
51 if(check(mid)) ans=min(ans,mid),r=mid;
52 else l=mid+1;
53 }
54 printf("%lld
",ans);
55 return 0;
56 }
