Wannafly Winter Camp 2020-Day7

w 本文总阅读量次

今天也还好？队伍EHK三题 我EH 虽然说E是打表的（

前一个小时状态极差 属于看什么什么不会 看H没有一点思路 感慨：他们怎么都会啊
手推了一下H前5项的情况 心里大概有了猜想 看了看ac队伍的用时也和想的式子一样 为了保险又手推了6 果然想的是对的 早知道莽了.jpg
但还是因为计算范围错了炸int了wa了一发 我是废物
过了H的生活因为K两个队友都在看 就去看新题了（加上我也不是很想推 开了E 又是手推了前几项 猜想了一个结论 顺利wa
然后考虑到了其他情况 继续推式子 但队友K还没过 遂帮倒忙地看了看K 因为真的懒得推 队友推了好几遍我相信式子没问题！又去看E
发现E在oeis直接有表 换Java写 因为语法不熟和改得太急成功wa*2
队友也把K过了 +10 排名从100开外变成50+ 最终排名60+吧 还行（

7E. 上升下降子序列

1
2
3
4
5
6
7
8
9
10
11
12
import java.math.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(); BigInteger m=sc.nextBigInteger();
        if(n==1){ System.out.println(0); return; }
        String[] s={"2","6","22","86","340","1340","5254","20518","79932","311028","1209916","4707964","18330728","71429176","278586182","1087537414","4249391468","16618640836","65048019092","254814326164","998953992728","3919041821896","15385395144092","60438585676636","237563884988120","934311596780040","3676495517376184","14474185732012088","57011153530262480","224656915621201776","885652912419210822","3492861836026915782","13780479845245611084","54388113081432337380","214729932989712917668","848052809484541707556","3350334574655466140216","13239822072430180232232","52335808270599440879284","206934571189982074002548","818425886045480073365896","3237673398479042349060632","12811192923571669467870664","50704290989642196738527048","200721767558683308700217776","794758327136359419952519952","3147480247103506996680796444","12467371711588974170827212188","49393251191799570968275635832","195721323613651013964116220008","775681930753017847189773247816","3074691375740439617836809788744","12189592067181565816702419563248","48333049189844665620128143125968","191674487676565550273850199554424","760234106384599142912931614646008","3015721572748589992463595600401200","11964485381977151314836595373090960","47473780481353767802050510461474416","188394767873878618122620614886243696","747717213262848575274466080605467552","2967958428851480386917331132533607136","11782259592346823520686656131742782022","46778706886870096588550881954439021894","185744202455399051984941117140485426188","737612707907218431744486755161165283876","2929451267263567016070637982850089264452","11635570442457473175795713890168152798404","46220155055609632689452725735280292076408","183618435592218742042711461696686422730216","729526765909664873244748736973027445604932","2898712749488697136757456372292134404034564","11518796733262965478081905854113416167753128","45776865583236473399203960989099899119494776","181937009594320978873736215406788995917525032","723154688965889751097101396443192826411889064","2874588225169330729910266250097039087510781168","11427560208426660761216674193001922526450403536","45432226748523983679867488376304124899523401012","180636860154887532842333974035976978875788303284","718256924308840704281727251872444612431548985768","2856167234882640332177000885696057331411192948216","11358398642653256630400822038234943728547172796632","45173065721576308057178968529470878470010061869784","179667842488623618336093016334593779472760809719248","714642491229551839105935178063714692911965481155696","2842722058240330382759816822753037594153543736276232","11308537787442034315752841106800792975560381040259464","44988801505636138725613585002139650894736930818859728","178989582482503853042943703302031527717732898643340656","712157265987568127773494228152764511315128648488823312","2833664093821898191595666210009358256743525029610686224","11275728828895114632325888269455044211548265118705668448","44870838790971390745360943764893423662680647193816689696","178569214591821033028866839352551169428060985661714360092","710675533602207732686301380136130771528525107574404678684","2828512285392854707326223033551336688181493890435185846968","11258130303537041119524653026082830440762998748471762960936","44812126024908558505907621010943168569218082391894548561192"};
        BigInteger q=new BigInteger(s[n-2]); q=q.mod(m);
        System.out.println(q);
    }
}

7H. 游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
const int mod = 998244353;
ll n,cnt,ans,num,g;
int main(){
   scl(n); rep(i,1,n+1) rep(j,i+1,n+1) if(__gcd(i,j)==1) cnt++;
   if(n==1) return puts("0/1"),0; if(n==2||n==3) return puts("1/1"),0;
   ans=n*(n-1)/2; num=n/2; g=__gcd(num*cnt,ans); pf("%lld/%lld\n",num*cnt/g,ans/g);
}

7K. 修炼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
int n,a1,a2,b1[maxn],b2[maxn];
int check(int x){
    ll t1=1ll*a1*x,t2=1ll*a2*x,mn=1e18; rep(i,1,n+1){
        ll res=0; if(t1>=b1[i]&&t2>=b2[i]) return 0;
        res+=b1[i]-t1>0?b1[i]-t1:0; res+=b2[i]-t2>0?b2[i]-t2:0;
        mn=min(mn,res);
    } return 1ll*x*(x+1)/2<mn;
}
int main(){
    cin>>a1>>a2>>n; rep(i,1,n+1) cin>>b1[i]>>b2[i];
    int l=-1,r=1e9; while(l<=r){
        int mid=l+r>>1; if(check(mid)) l=mid+1; else r=mid-1;
    } pf("%d\n",l);
}
w