UOJ Round #3
http://vfleaking.blog.uoj.ac/blog/43
「UR #3」核聚变反应强度
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 9000000000000000000LL #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,top; int q[105]; ll a[100005]; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } void solve(ll x) { for(int i=1;i<=top;i++) if(x%q[i]==0) { printf("%lld ",x/q[i]); return; } if(x!=1)printf("1 "); else printf("-1 "); } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); ll x=a[1]; for(int i=2;i<=sqrt(x);i++) if(x%i==0) { while(x%i==0)x/=i; q[++top]=i; } for(int i=1;i<=n;i++) solve(gcd(a[1],a[i])); return 0; } |
「UR #3」铀仓库
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 9000000000000000000LL #define mp make_pair #define pa pair<ll,ll> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int x[500005],a[500005]; ll s[500005],t; ll dis(int a,int b) { return x[b]-x[a]; } ll sum(int l,int lc,int r,int rc) { return l==r?rc-lc:s[r-1]-s[l]+a[l]-lc+rc; } bool check(ll x) { int l=1,r=n+1,lc=0,rc=0; ll val=0; for(int i=1;i<=n;i++) if(s[i]<=x)val+=dis(1,i)*a[i]; else {r=i;rc=x-s[i-1];val+=dis(1,i)*rc;break;} if(val<=t)return 1; for(int i=2;i<=n;i++) { val+=dis(i-1,i)*(sum(l,lc,i,0)-sum(i,0,r,rc)); while(r<=n&&dis(l,i)>dis(i,r)) { int z=min(a[l]-lc,a[r]-rc); val+=(dis(i,r)-dis(l,i))*z; lc+=z;if(lc==a[l])l++,lc=0; rc+=z;if(rc==a[r])r++,rc=0; } if(val<=t)return 1; } return 0; } int main() { n=read();t=read();t/=2; for(int i=1;i<=n;i++)x[i]=read(); for(int i=1;i<=n;i++)a[i]=read(),s[i]=s[i-1]+a[i]; ll l=0,r=s[n],ans=0; while(l<=r) { ll mid=(l+r)>>1; if(check(mid))ans=mid,l=mid+1; else r=mid-1; } printf("%lld\n",ans); return 0; } |
「UR #3」链式反应
题目都不敢看。。。
Subscribe
计数器 9319814
OI 课件=>
OI 课件=>