CF #278
不参加
A:やるだけ
B:過去のある範囲maxのDP→segtree
C:{0,-1,+2,-3}(mod 4)とかで部分和で全種類出てくる
C気づかないのが幼稚園児
A.cpp
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second #define pb push_back #define show(x) cout << #x << " " << x << endl int main(){ int myh,mya,myd,eh,ea,ed,uph,upa,upd; cin>>myh>>mya>>myd>>eh>>ea>>ed>>uph>>upa>>upd; int ans=1e9; rep(i,300){ int a=mya+i; if(a<=ed) continue; int t=(eh+a-ed-1)/(a-ed); rep(j,300){ int money=i*upa+j*upd; int d=myd+j; if(d>=ea){ ans=min(ans,money); break; } int dam=ea-d; int needhp=t*dam+1; if(needhp<=myh){ ans=min(ans,money); }else{ ans=min(ans,money+(needhp-myh)*uph); } } } cout<<ans<<endl; }
B.cpp
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second #define pb push_back #define show(x) cout << #x << " " << x << endl const int p2=1<<17; int n,s,l,a[100000],r[100000],seg[p2*2]; multiset<int> msi; void update(int x){ while(true){ x=(x-1)/2; seg[x]=min(seg[x*2+1],seg[x*2+2]); if(x==0) break; } } int inf=1e8; int segmin(int a,int b,int l,int r,int k){ if(a>=b) return inf; if(b<=l||r<=a) return inf; if(a<=l&&r<=b) return seg[k]; return min(segmin(a,b,l,(l+r)/2,k*2+1),segmin(a,b,(l+r)/2,r,k*2+2)); } int main(){ cin>>n>>s>>l; rep(i,n) cin>>a[n-1-i]; int it=0; bool ok=false; rep(i,n){ int mn=0,mx=0; if(!msi.empty()) mn=*(msi.begin()),mx=*(msi.rbegin()); while(mx-mn<=s){ if(it==n){ ok=true; break; } msi.insert(a[it]); mn=*msi.begin(),mx=*(msi.rbegin()); it++; } r[i]=it-2; if(ok) r[i]=n-1; msi.erase(msi.lower_bound(a[i])); } reverse(r,r+n); rep(i,n) r[i]=n-1-r[i]; // rep(i,n) show(r[i]); rep(i,p2*2-1) seg[i]=inf; seg[p2-1]=0; update(p2-1); rep1(i,n){ seg[p2-1+i]=1+segmin(r[i-1],i-l+1,0,p2,0); update(p2-1+i); } int ans=seg[p2-1+n]; if(ans>=inf) ans=-1; cout<<ans<<endl; }
C.cpp
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second #define pb push_back #define show(x) cout << #x << " " << x << endl typedef long long ll; const int ccc=100000; bool prime[ccc+1]; vector<int> pr; void makeprime(){ int i,j; for(i=2;i<=ccc;i++) prime[i]=true; for(i=2;i*i<=ccc;i++) if(prime[i]) for(j=2;j*i<=ccc;j++) prime[j*i]=false; for(i=2;i<=ccc;i++) if(prime[i]) pr.push_back(i); } int p[ccc+1]; int main(){ makeprime(); int n; cin>>n; if(n==1){ puts("YES"); puts("1"); return 0; } if(n==4){ puts("YES"); printf("1\n3\n2\n4\n"); return 0; } if(!prime[n]){ puts("NO"); return 0; } int g=2; for(;;g++){ ll now=1; bool can=true; rep(i,n/2){ now*=g; now%=n; if(now==1){ can=false; break; } } if(!can) continue; p[0]=1; rep(i,n) p[i+1]=p[i]*g%n; puts("YES"); rep(i,n-1){ if(i%2==0) cout<<p[i]<<" "; else cout<<p[n-1-i]<<" "; } cout<<n<<endl; return 0; } }