http://codeforces.com/contest/678
A：水题
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=200000+10,maxn=400000+10,inf=0x3f3f3f3f; int main() { int n,k; scanf("%d%d",&n,&k); if(n%k==0)printf("%d ",n+k); else printf("%d ",((int)(n/k)+1)*k); return 0; } /******************** ********************/
B：题意有点难懂，意思就是给你一个年份n，要求你找到下一个每天都和n相同的年份（指该年的第一天星期和n年相同，天数也相同）
解法：直接暴力，求天数的综合，判断能不能整除7，还有是不是闰年即可
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=200000+10,maxn=400000+10,inf=0x3f3f3f3f; bool leap(int x) { return x%400==0||(x%4==0&&x%100!=0); } int main() { // cout<<(3*365+366)%7<<endl; int y; scanf("%d",&y); ll te=0; for(int i=y;;i++) { if(leap(i))te+=366; else te+=365; if(te%7==0) { if(leap(y)==leap(i+1)) { printf("%d ",i+1); return 0; } } } return 0; } /******************** ********************/
C：题意：给n个块，整除a可以填红色，整除b可以填蓝色，红色和蓝色的块分别有一个价值，求填完的最大值
解法：先1到n，整除a的填上，整除b的填上，然后会出现重复，我们把能整除a，b的删掉价值小的那个颜色
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=200000+10,maxn=400000+10,inf=0x3f3f3f3f; int main() { ll n,a,b,p,q; scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&p,&q); ll aa=n/a; ll bb=n/b; if(p>q)bb-=n/(a/__gcd(a,b)*b); else aa-=n/(a/__gcd(a,b)*b); printf("%lld ",p*aa+q*bb); return 0; } /******************** ********************/
D：给你一个递推式g(x)^n=a*g(x)^(n-1)+b,g(x)^0=x,给你abxn，求g(x)^n的值
很明显的矩阵快速幂，递推关系式是
(g(x)^n)=( a b)(g(x)^(n-1))
( 1 )=(0 1)( 1 )
也可以用推公式然后逆元搞，公式是g(x)^n=a^n*x+b*(1-a^n)/(1-a)
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=20+10,maxn=400000+10,inf=0x3f3f3f3f; struct Node{ ll row,col; ll a[N][N]; }; Node mul(Node x,Node y) { Node ans; memset(ans.a,0,sizeof ans.a); ans.row=x.row,ans.col=y.col; for(ll i=0;i<x.row;i++) for(ll j=0;j<y.row;j++) for(ll k=0;k<y.col;k++) ans.a[i][k]=(ans.a[i][k]+x.a[i][j]*y.a[j][k]+mod)%mod; return ans; } Node quick_mul(Node x,ll n) { Node ans; ans.row=x.row; ans.col=x.col; memset(ans.a,0,sizeof ans.a); for(int i=0;i<ans.row;i++)ans.a[i][i]=1; while(n){ if(n&1)ans=mul(ans,x); x=mul(x,x); n/=2; } return ans; } ll quick(ll a,ll b) { ll ans=1; while(b) { if(b&1)ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int main() { ll aa,bb,n,x; scanf("%lld%lld%lld%lld",&aa,&bb,&n,&x); Node A,B; A.row=2,A.col=2; A.a[0][0]=aa,A.a[0][1]=bb; A.a[1][0]=0,A.a[1][1]=1; B.row=2,B.col=1; B.a[0][0]=x; B.a[1][0]=1; ll ans=(mul(quick_mul(A,n),B).a[0][0]+mod)%mod; printf("%lld ",ans); return 0; } /******************** ********************/
E：有n个人相互决斗，给出i赢j的概率，要求找一种安排方案，让1号选手获胜的最大概率
状压（概率）dp，由于从赢到输不太好处理，于是我们考虑从输到赢逆推，
用dp[i][j]表示i状态下，j是当前擂主的1号最后获胜的最大概率
当i状态下j，k都是存活的，那么dp[i][j]可以转移到dp[i^(1<<k)][j]，此时j是擂主，j和k打，k输，也可以转移到dp[i^(1<<j)][k]，此时j是擂主，j和k打，j输，再乘上获胜的概率即可
有转移方程dp[i][j]=max(dp[i][j],dp[i^(1<<j)][k]*win[k][j]+dp[i^(1<<j)][k]*win[j][k]);
当只有1号时，存活概率为1，因此，边界值dp[1][0]=1;最后从所有人都存活的状态中找概率最大的即可
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=300000+10,maxn=400000+10,inf=0x3f3f3f3f; double dp[N][20]; double win[20][20]; int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%lf",&win[i][j]); dp[1][0]=1; for(int i=0;i<(1<<n);i++) { for(int j=0;j<n;j++) { if((i>>j)&1) { for(int k=0;k<n;k++) { if(j==k)continue; if((i>>k)&1) { dp[i][j]=max(dp[i][j],dp[i^(1<<j)][k]*win[k][j]+dp[i^(1<<k)][j]*win[j][k]); } } } } } double ans=0.0; for(int i=0;i<n;i++) ans=max(ans,dp[(1<<n)-1][i]); printf("%.12f ",ans); return 0; } /******************** ********************/
F：题意：n个操作，第一种是加一个二元组{x，y}到集合中，第二种删除i号操作加入的二元组，第三种给你一个p，求集合中最大的x*p+y
解法：对于第三种操作假设b=x*p+y,y=-p*x+b,那么就是求经过x，斜率为-p直线的截距，那么我们可以维护一个凸包来求解，当然直接遍历凸包上的点肯定是不行的，所以我们画出凸包的图，假设p为负数，那么我们从第三象限扫一遍到第一象限，可以看出对于凸包上的点，这个截距是单峰的，也因为凸包上的点是有序的，可以得出无论p是多少，结果对于凸包上的有序点来说肯定是单峰的，那么我们可以用三分来求解。
还有一个问题是这个凸包是动态的，我们不能每次都扫一遍凸包，这样太费时了，可以看出对于每一个加入的二元组，它都有一个作用时间区间，我们可以对这个时间区间建立一颗线段树，每个节点维护在该时间区间出现的二元组，（这样我们就同时解决了操作1和操作2），建好线段树之后，我们对每一个节点求一次凸包，当查询时，我们在线段树上走一遍对每个点三分一下，找出最大的值即可
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define inf 9223372036854775807ll #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=300000+10,maxn=400000+10; struct point{ ll x,y; point(ll x=0,ll y=0):x(x),y(y){} bool operator <(const point &rhs)const{ return x<rhs.x||(x==rhs.x&&y<rhs.y); } point operator +(const point &rhs)const{ return point(x+rhs.x,y+rhs.y); } point operator -(const point &rhs)const{ return point(x-rhs.x,y-rhs.y); } ll operator *(const point &rhs)const{ return x*rhs.y-y*rhs.x; } }p[N]; int en[N]; ll ask[N],ans; vector<point>pointset[N<<2]; void update(int L,int R,int l,int r,int rt) { // printf("%d------%d ",l,r); if(L<=l&&r<=R) { // puts("+++++++++++"); pointset[rt].pb(p[L]); return ; } int m=(l+r)>>1; if(L<=m)update(L,R,ls); if(m<R)update(L,R,rs); } void dfs(int l,int r,int rt) { vector<point>& v=pointset[rt]; if(!v.empty())sort(v.begin(),v.end()); if(v.size()>2) { int i,j; for(i=2,j=1;i<v.size();i++) { while(j>0&&(v[j]-v[j-1])*(v[i]-v[j])>=0)j--; j++; v[j]=v[i]; } while(v.size()>j+1)v.pop_back(); } if(l==r)return ; int m=(l+r)>>1; dfs(ls);dfs(rs); } ll fun(point p,ll v){return p.x*v+p.y;} ll solve(vector<point> &v,ll c) { ll ans=-inf; int l=0,r=v.size()-1; while(r-l>6) { int m1=(l*2+r)/3; int m2=(l+r*2)/3; if(fun(v[m1],c)<fun(v[m2],c))l=m1; else r=m2; } for(int i=l;i<=r;i++)ans=max(ans,fun(v[i],c)); return ans; } void query(int pos,ll c,int l,int r,int rt) { ans=max(ans,solve(pointset[rt],c)); if(l==r)return; int m=(l+r)>>1; if(pos<=m)query(pos,c,ls); else query(pos,c,rs); } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { en[i]=-1; ask[i]=-inf; int t; scanf("%d",&t); if(t==1) { scanf("%lld%lld",&p[i].x,&p[i].y); en[i]=n; } else if(t==2) { int x; scanf("%d",&x); en[x]=i-1; } else { scanf("%lld",&ask[i]); } } for(int i=1;i<=n;i++) if(en[i]!=-1) update(i,en[i],1,n,1); dfs(1,n,1); // for(int i=0;i<pointset[1].size();i++) // { // point te=pointset[1][i]; // printf("%lld %lld ",te.x,te.y); // } for(int i=1;i<=n;i++) { if(ask[i]!=-inf) { ans=-inf; query(i,ask[i],1,n,1); if(ans==-inf)puts("EMPTY SET"); else printf("%lld ",ans); } } return 0; } /******************** ********************/