Wannafly Winter Camp 2020-Day7

今天也还好?队伍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);
}