CQOI2015终于全做完了~~~，讲一下题吧
首先这套题比起其他省选还是比较水的，就是5道题比较蛋疼
T1：[CQOI2015]选数
这道题还是比较神的。
首先给个比较神的题解：popoqqq大神的blog这个莫比乌斯反演真的不会
我们记f[i]为gcd=i*k时的个数，可以得到若数都不相等的话，i一定小于1e5（辗转相减法可得），那么当数都不相等时，答案显然为(r/(k*i)-l/(k*i)+1)^n-(r/(k*i)-l/(k*i)+1)-sigma(f[i*j])然后就能愉快的推出来啦，还有就是当l=1时要特判一下
CODE：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define mod 1000000007
typedef long long ll;
int power(ll x,ll y) {
ll ans=;
for (;y;y>>=){
if (y&) (ans*=x)%=mod;
(x*=x)%=mod;
}
return ans;
}
ll n,l,k,h;
#define maxk 100000
ll f[maxk+];
int main(){
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
ll L,H;
scanf("%lld%lld%lld%lld",&n,&k,&L,&H);
ll l=L/k,h=H/k;
if (L%k) l++;
int tmp=;
for (int i=maxk;i;i--) {
ll L=l/i,H=h/i;
if (l%i) L++;
f[i]=(power(H-L+,n)-(H-L+)+mod)%mod;
for (int j=i+i;j<=maxk;j+=i) f[i]=(f[i]-f[j]+mod)%mod;
}
if (l==) f[]++;
printf("%lld\n",f[]);
return ;
}
这不就是先求出最短路图后拆点跑个最大流么= =。直接做就行了不要考虑时间问题。。。
CODE：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
#define maxm 150000
#define maxn 1100
struct edges{
int to,next,dist;ll cap;
}edge[maxm*];
int l,next[maxn];
inline void _addedge(int x,int y,int z){
l++;
edge[l*]=(edges) {x,next[y],z,};next[y]=l*;
edge[l*+]=(edges) {y,next[x],z,};next[x]=l*+;
}
inline void addedge(int x,int y,ll z){
l++;
edge[l*]=(edges){y,next[x],,z};next[x]=l*;
edge[l*+]=(edges){x,next[y],,};next[y]=l*+;
}
ll dist[maxn];
bool b[maxn];
typedef pair<ll,int> ii;
priority_queue<ii,vector<ii>,greater<ii> > q;
#define fi first
#define se second
#define inf 0x7fffffff
#define Inf inf*1ll*inf
int n;
inline void dij(){
for (int i=;i<=n;i++) dist[i]=Inf;
dist[]=;
q.push(ii(,));
while (!q.empty()){
ii u=q.top();q.pop();
if (b[u.se]) continue;
b[u.se]=;
for (int i=next[u.se];i;i=edge[i].next)
if (dist[u.se]+edge[i].dist<dist[edge[i].to]) {
dist[edge[i].to]=dist[u.se]+edge[i].dist;
q.push(ii(dist[edge[i].to],edge[i].to));
}
}
}
int p[maxn],gap[maxn],h[maxn],s,t,N;
ll sap(int u,ll flow){
if (u==t) return flow;
ll cnt=;
for (int i=p[u];i;i=edge[i].next)
if (edge[i].cap&&h[edge[i].to]+==h[u]) {
ll cur=sap(edge[i].to,min(edge[i].cap,flow-cnt));
edge[i].cap-=cur;edge[i^].cap+=cur;
p[u]=i;
if ((cnt+=cur)==flow) return flow;
}
if (!(--gap[h[u]])) h[s]=N;
gap[++h[u]]++;
p[u]=next[u];
return cnt;
}
inline ll maxflow(){
for (int i=;i<=N;i++) p[i]=next[i];
ll flow=;
gap[]=N;
while (h[s]<N) flow+=sap(s,Inf);
return flow;
}
int main(){
freopen("network.in","r",stdin);
freopen("network.out","w",stdout);
int m;
scanf("%d%d",&n,&m);
N=n*;
for (int i=;i<=m;i++) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
_addedge(x,y,z);
}
dij();
memset(next,,sizeof(next));
l=;
for (int i=;i<=m*+;i+=) {
if (dist[edge[i].to]==dist[edge[i^].to]+edge[i].dist)
addedge(n+edge[i^].to,edge[i].to,Inf);
else if (dist[edge[i^].to]==dist[edge[i].to]+edge[i^].dist)
addedge(n+edge[i].to,edge[i^].to,Inf);
}
for (int i=;i<=n;i++) {
int x;
scanf("%d",&x);
addedge(i,n+i,x);
}
s=+n,t=n;
printf("%lld\n",maxflow());
return ;
}
T3：[CQOI2015]任务查询系统
描述：戳我~~~
这道题首先很明显是道裸的数据结构题啦。首先他要求在线，那么按顺序建个函数式线段树就行啦
自己太弱调了好久= =
CODE：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define pb push_back
#define maxn 100100
struct qnode{
int x,y,z;
}q[maxn*];
int l;
inline void add(int x,int y,int z) {q[++l]=(qnode){x,y,z};}
bool cmp(qnode x,qnode y) {return x.x<y.x;}
struct node{int lc,rc,sum;ll s;}t[maxn*];
#define mid (l+r>>1)
int cnt=;
int ins(int x,int l,int r,int y,int z){
int root=++cnt;
t[root]=t[x];
t[root].s+=y*z;
t[root].sum+=z;
if (l==r) return root;
if (y<=mid) t[root].lc=ins(t[x].lc,l,mid,y,z);
else t[root].rc=ins(t[x].rc,mid+,r,y,z);
return root;
}
ll que(int x,int l,int r,int &k){
if (t[x].sum<=k) {
k-=t[x].sum;return t[x].s;
}
if (l==r) {ll ans=l*1ll*k;k=;return ans;}
ll ans=que(t[x].lc,l,mid,k);
if (k) ans+=que(t[x].rc,mid+,r,k);
return ans;
}
vector<int> a;
int s[maxn],e[maxn],p[maxn],root[maxn];
int main(){
int n,m;
scanf("%d%d",&n,&m);
a.pb();
for (int i=;i<=n;i++) {
scanf("%d%d%d",s+i,e+i,p+i);
e[i]++;
a.pb(s[i]);a.pb(e[i]);
}
sort(a.begin(),a.end());
a.resize(unique(a.begin(),a.end())-a.begin());
for (int i=;i<=n;i++) {
add(lower_bound(a.begin(),a.end(),s[i])-a.begin(),p[i],);
add(lower_bound(a.begin(),a.end(),e[i])-a.begin(),p[i],-);
}
sort(q+,q++l,cmp);
#define inf 10000000
for (int i=;i<=l;i++) root[q[i].x]=ins(root[q[i-].x],,inf,q[i].y,q[i].z);
ll pre=;
for (int i=;i<=m;i++) {
int x,ai,bi,ci;
scanf("%d%d%d%d\n",&x,&ai,&bi,&ci);
int k=1ll+(ai*1ll*(pre%ci)%ci+bi)%ci;
pre=que(root[upper_bound(a.begin(),a.end(),x)-a.begin()-],,inf,k);
printf("%lld\n",pre);
}
return ;
}
T4：[CQOI2015]多项式
描述：戳我~~~
又是高精度= =
首先我们可以换一下元，吧x-t换成x那就能得到
那么
就能算5次即可啦，再考虑怎么快速算组合数
完成啦
CODE：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxb 4
using namespace std;
char s[];
int p[]={,,,,,,,,};
struct bignum{
int a[],n,flag;
bignum(int x){
n=;memset(a,,sizeof(a));
flag=x<?:;x=abs(x);
while (x) {a[++n]=x%p[maxb];x/=p[maxb];}
if (!n) n=;
}
bignum(){n=;memset(a,,sizeof(a));flag=;}
int read(){
scanf("%s",s);
int len=strlen(s);
n=;
if (len==&&s[]=='') {a[n=]=;return ;}
for (int i=len;i>=;i-=maxb) {
int t=;
if (i>maxb) for (int j=i-maxb+;j<=i;j++) t=t*+s[j-]-'';
else for (int j=;j<=i;j++) t=t*+s[j-]-'';
a[++n]=t;
}
return ;
}
int write(){
if (flag) printf("-");
printf("%d",a[n]);
for (int i=n-;i>=;i--) {
for (int j=;j<maxb;j++) if (a[i]<p[j]) printf("");
printf("%d",a[i]);
}
printf("\n");
return ;
}
int cmp(bignum x){
if (x.n!=n) return (x.n<n);
for (int i=n;i>=;i--)
if (x.a[i]!=a[i]) return (x.a[i]<a[i]);
return -;
}
int div(int x){
int s=;
for (int i=n;i>=;i--){
s=a[i]+s*p[maxb];
a[i]=s/x;
s%=x;
}
if (n!=&&!a[n]) n--;
return s;
}
}a,b;
bignum operator + (bignum x,bignum y){
if (x.flag^y.flag && x.cmp(y)==)swap(x,y);
if (x.flag==y.flag) {
x.n=max(x.n,y.n);
for (int i=;i<=x.n;i++) {
x.a[i]+=y.a[i];
x.a[i+]+=x.a[i]/p[maxb];
x.a[i]%=p[maxb];
}
if (x.a[x.n+]) x.n++;
return x;
}
for (int i=;i<=x.n;i++) {
x.a[i]-=y.a[i];
if (x.a[i]<) {x.a[i]+=p[maxb];x.a[i+]--;}
while (!x.a[x.n]&&x.n>) x.n--;
}
return x;
}
bignum operator * (bignum x,bignum y){
bignum ans;
if (x.n==&&x.a[]==) return ans;
if (y.n==&&y.a[]==) return ans;
ans.flag=x.flag^y.flag;
for (int i=;i<=x.n;i++)
for (int j=;j<=y.n;j++) {
ans.a[i+j-]+=x.a[i]*y.a[j];
ans.a[i+j]+=ans.a[i+j-]/p[maxb];
ans.a[i+j-]%=p[maxb];
}
int n=x.n+y.n-;
while (ans.a[n+]) {
n++;ans.a[n+]+=ans.a[n]/p[maxb];
ans.a[n]%=p[maxb];
}
ans.n=n;
return ans;
}
int sum;
int main(){
static bignum n,m;
int t;
n.read();
scanf("%d",&t);
m.read();
static int a[];
a[]=;
for (int i=;i<=;i++) a[i]=(a[i-]*+) % ;
static bignum tmp=m;
int l=tmp.div();
static bignum ans,c=bignum(),T=bignum();
int cnt=;
for (bignum i=m;i.cmp(n)!=;i=i+bignum(),cnt++) {
ans=ans+c*T*bignum(a[l]);
l=(l+)%;
c=c*(i+bignum());
c.div(cnt+);
T=T*bignum(t);
}
ans.write();
return ;
}
T5:[CQOI2015]标示设计
描述：戳我~~~
首先我们考虑轮廓线，那么每个L可能有四种状态：已经结束，还未开始，还没拐弯，已经拐弯，那么如果从上到下，从左到右做的话，可以发现最多只有3条横边被标记，那么对每个L我们可以用一维来存这个状态，在加上起始状态还有终止状态就行啦，然后已经拐弯的状态一定是在那条竖边上在讨论下就行啦
由于我是从左到右，从上到下做的，所以每一维就多了1倍的状态，所以在BZ上就光荣的TLE啦，不过在学校的oj上还是能过的。所以代码就不贴啦