枚举/二分
C题太神窝看不懂……
核聚变反应强度
QwQ很容易发现次小的公约数一定是gcd的一个约数，然后……我就傻逼地去每次算出a[1],a[i]的gcd，然后枚举约数……这复杂度……哦呵呵。。。
正解是先找到a[1]的所有质因数啊……然后在刚刚那个算法的“枚举gcd的约数”的时候直接枚举这些质因数就好了……
//UOJ Round3 A
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline LL getint(){
LL r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=(v<<)+(v<<)-''+ch;
return r*v;
}
const int N=1e6+;
/*******************template********************/ int n,tot,cnt;
LL a[N],b[N],prime[N];
bool vis[N];
inline LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
#endif
n=getint();
F(i,,n) a[i]=getint();
for(LL i=;i*i<=a[];i++)
if (!vis[i]){
prime[++tot]=i;
for(LL j=i+i;j*j<=a[];j+=i) vis[j]=;
}
F(i,,tot) if (a[]%prime[i]==) b[++cnt]=prime[i];
LL tmp;
F(i,,n){
tmp=gcd(a[],a[i]);
if (tmp==) {printf("-1 "); continue;}
bool sign=;
F(j,,cnt)
if (tmp%b[j]==){
printf("%lld ",tmp/b[j]);
sign=;
break;
}
if (sign) printf("1 ");
}
return ;
}
铀仓库
题解好神啊……如果要直接计算T时间以内能搬几个箱子，那么我们需要枚举s，然后再算每个s在T时间内能搬多少。
一看就感觉要爆呀。。。
解决方法是二分= =将最优性问题转化成判定性问题，现在我们的问题就是：给定一个箱子数量K，问最短的时间是多少。
这样的话我们仍旧可以枚举s，但是由于箱子数是固定的，所以我们根据s-1的答案可以比较方便地得到s的答案。
实现细节方面：我们在放弃左端点箱子而去搬右端点箱子的时候，需要维护一下是哪边先归零……然而我写分类讨论写了好长啊……而@delayyy神犇很简短的就处理完了……事实上我好像想多了……并不需要分类讨论……只要每次取最小值？。。。就可以了……
//UOJ Round3 B
//orz delayyy
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=5e5+;
/*******************template********************/ int n,a[N],x[N],use[N];
LL t,s[N];
inline LL d(int i,int j){return x[j]-x[i];}
inline LL sum(int l,int lc,int r,int rc){
return l==r ? rc-lc : s[r-]-s[l]+a[l]-lc+rc;
}
bool check(LL K){
int l=,lc=,r=n+,rc=; LL cur=,sa=;
F(i,,n){
if (sa+a[i]<=K) sa+=a[i],cur+=d(,i)*a[i];
else {r=i,rc=K-sa,cur+=d(,i)*rc; break;}
}
if (cur<=t) return ; F(i,,n){
cur+=d(i-,i)*(sum(l,lc,i,)-sum(i,,r,rc));
while(r<=n && d(l,i)>d(i,r)){
int z=min(a[l]-lc,a[r]-rc);
cur+=(d(i,r)-d(l,i))*z;
if (lc+=z,lc>=a[l]) ++l,lc=;
if (rc+=z,rc>=a[r]) ++r,rc=;
}
if (cur<=t) return ;
}
return ;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
#endif
n=getint(); scanf("%lld",&t); t/=;
F(i,,n) x[i]=getint();
F(i,,n) a[i]=getint(),s[i]=s[i-]+a[i]; LL L=,R=s[n],mid,ans=;
while(L<=R){
mid=L+R>>;
if (check(mid)) ans=mid,L=mid+;
else R=mid-;
}
printf("%lld\n",ans);
return ;
}