2018-07-26
4维费用背包, 注意得用char或short.
#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#define mst(a, b) memset(a, b, sizeof(a))
#define clr(a) mst(a, 0)
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define lowbit(x) (x&(-x))
#define fi first
#define se second
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (b); i >= (a); i--)
#define lt u << 1
#define rt u << 1 | 1
#define pr(x) cout << #x << " = " << x << " ";
#define prl(x) cout << #x << " = " << x << endl;
using namespace std;
template<typename T>
ostream& operator << (ostream & os, const vector<T>& v) {
for(int i = 0; i < v.size(); i++) os << v[i] << " ";
}
template<typename T>
ostream& operator << (ostream & os, const set<T>& v) {
for(typename set<T>::iterator it = v.begin(); it != v.end(); it++) os << *it << " ";
}
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> V;
typedef pair<int, int> P;
typedef long double LDB;
typedef double DB;
int n;
int v[40][6];
int w[6];
int dp[37][37][37][37];
bool ch[37][37][37][37][37];
int id[37][37][37][37];
V ans;
int main() {
//freopen("a.in", "r", stdin);
scanf("%d", &n);
rep(i, 1, n) {
rep(j, 0, 4) {
scanf("%d", &v[i][j]);
}
}
rep(i, 0, 3) {
scanf("%d", w + i);
}
rep(i, 1, n) {
per(p, v[i][0], w[0]) {
per(a, v[i][1], w[1]) {
per(c, v[i][2], w[2]) {
per(m, v[i][3], w[3]) {
//ch[i][p][a][c][m] = ch[i - 1][p][a][c][m];
if(dp[p][a][c][m] < dp[p - v[i][0]][a - v[i][1]][c - v[i][2]][m - v[i][3]] + v[i][4]) {
dp[p][a][c][m] = dp[p - v[i][0]][a - v[i][1]][c - v[i][2]][m - v[i][3]] + v[i][4];
ch[i][p][a][c][m] = 1;
//ch[i][p][a][c][m] = ch[i - 1][p - v[i][0]][a - v[i][1]][c - v[i][2]][m - v[i][3]];
} else ch[i][p][a][c][m] = 0;
}
}
}
}
}
//dfs(n, w[0], w[1], w[2], w[3]);
int pp = w[0], aa = w[1], cc = w[2], mm = w[3];
for(int i = n; i >= 1; i--) {
if(ch[i][pp][aa][cc][mm]) {
ans.pb(i);
pp -= v[i][0], aa -= v[i][1], cc -= v[i][2], mm -= v[i][3];
}
}
cout << sz(ans) << endl;
rep(i, 0, sz(ans) - 1) {
printf("%d", ans[i] - 1);
if(i < sz(ans) - 1) printf(" ");
}
return 0;
}
splay基本操作,区间分割,区间合并
/* ***********************************************
Author :JiangYu
Created Time :2018年07月27日 星期五 17时11分10秒
File Name :splay.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x)&(-x)
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define getlc(a) ch[(a)][0]
#define getrc(a) ch[(a)][1]
#define maxn 200000
#define maxm 100000
#define pi 3.1415926535898
#define _e 2.718281828459
#define INF 1070000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//template<class T> inline
//void read(T& num) {
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x)&(-x)
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define getlc(a) ch[(a)][0]
#define getrc(a) ch[(a)][1]
#define maxn 200000
#define maxm 100000
#define pi 3.1415926535898
#define _e 2.718281828459
#define INF 1070000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//template<class T> inline
//void read(T& num) {
//bool start=false,neg=false;
//char c;
//num=0;
//while((c=getchar())!=EOF) {
//if(c==‘-‘) start=neg=true;
//else if(c>=‘0‘ && c<=‘9‘) {
//start=true;
//num=num*10+c-‘0‘;
//} else if(start) break;
//}
//if(neg) num=-num;
//}
/*==================split line==================*/
int n,m;
int v[maxn],s[maxn],ch[maxn][2],fa[maxn],flip[maxn];
int cnt=0,root,null;
void updata(int node){s[node]=s[getlc(node)]+s[getrc(node)]+1;}
int build(int sz){
if (sz<=0) return 0;
int t=build(sz/2),node=++cnt;
fa[ch[node][0]=t]=node;
t=build(sz-sz/2-1); fa[ch[node][1]=t]=node;
v[node]=node-1; updata(node);
return node;
}
//void pushdown(int x){
//if (!flip[x]) return;
//flip[x]=0;
//flip[getlc(x)]^=1; flip[getrc(x)]^=1;
//swap(ch[x][0],ch[x][1]);
//}
void rotate(int x){
int p=fa[x],q=fa[p],d=ch[p][1]==x;
//pushdown(x);
fa[ch[p][d]=ch[x][d^1]]=p; updata(p);
fa[ch[x][d^1]=p]=x; updata(x);
fa[x]=q;
if (q){
if (ch[q][0]==p) ch[q][0]=x;
else if(ch[q][1]==p) ch[q][1]=x;
}
}
void splay(int x,int &aim){
for(int y;(y=fa[x])!=aim;rotate(x))
if (fa[y]!=aim) rotate((getlc(y)==x)==(getrc(fa[y])==y)?y:x);
if (aim==0) root=x;
updata(x);
}
int kth(int node, int k){
int x=node;
while (x){
//pushdown(x);
int ss=0;
if (ch[x][0]!=0) ss=s[ch[x][0]];
if (k==ss+1) return x;
if (k<=ss) x=ch[x][0];
else if (k>ss+1) x=ch[x][1],k-=ss,k--;
}
return x;
}
void change(int l,int r){
int node=kth(root,l); splay(node,null);
node=kth(getrc(root),r-l+2); splay(node,root);
int t=getlc(getrc(root));
//flip[t]^=1;
getlc(getrc(root))=0;
updata(getrc(root)); updata(root);
int k=0;
node=kth(root,k+1); splay(node,null);
node=kth(getrc(root),1); splay(node,root);
fa[t]=getrc(root); getlc(getrc(root))=t;
updata(getrc(root)); updata(root);
}
void print(int node){
if (node==0) return;
//////pushdown(node);
print(ch[node][0]);
if (node!=1 && node!=n+2) printf("%d ",node-1);
print(ch[node][1]);
}
int main(){
scanf("%d%d", &n, &m);
memset(flip,0,sizeof(flip));
root=build(n+2);
FORP(i,1,m){
int x,y;
scanf("%d%d", &x, &y);
y = x + y - 1;
change(x,y);
//print(root);
}
print(root);
}
另F(D) 为最小距离大于等于D时,方案数量, 则F(D) - F(D+1) 即为最小距离等于D的数量.
先dfs一遍,预处理出每个点与其他点的距离.然后从根节点开始bfs染色. 对于每个点,可染色的数量为k-x, x为距离小于D的数量. 最后全部乘起来就好了. 而bfs可以保证,我们处理的顺序一定是当前点和处理过的点,两两距离都在D以内.
/* ***********************************************
Author :JiangYu
Created Time :2018年07月27日 星期五 19时58分18秒
File Name :g.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
const int N = 5000 + 256;
const int mod = 1e9 + 7;
vector<int> g[N];
int n, k, d;
int dis[N][N];
#define ll long long
#define PB push_back
void dfs(int s, int u, int fa = 0) {
for(int v : g[u]) {
if(v == fa) continue;
dis[s][v] = dis[s][u] + 1;
dfs(s, v, u);
}
}
int val[N];
ll solve(int way) {
queue<int> q;
q.push(1);
for(int i = 1; i <= n; ++i) val[i] = k;
ll ans = 1;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int v = 1; v <= n; ++v)
if( u != v)
val[v] -= dis[u][v] < way;
if(val[u] <= 0) return 0;
ans = ans*val[u]%mod;
for(int v : g[u]) {
if(dis[1][u] + 1 == dis[1][v])
q.push(v);
}
}
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d%d%d", &n, &k, &d);
for(int i = 1; i < n; ++i) {
int u, v;
scanf("%d%d", &u, &v);
g[u].PB(v);
g[v].PB(u);
}
for(int i = 1; i <= n; ++i) {
dfs(i, i);
}
printf("%lld", (solve(d) - solve(d+1) + mod) % mod);
return 0;
}
板子题,哭泣
/* ***********************************************
Author :JiangYu
Created Time :2018年07月27日 星期五 21时46分48秒
File Name :j.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const double PI = acos(-1.0);
int dcmp(double x)
{
if( x > eps ) return 1;
return x < -eps ? -1 : 0;
}
struct Point
{
double x,y;
Point()
{
x = y = 0;
}
Point(double a,double b)
{
x = a;
y = b;
}
inline void input()
{
scanf("%lf%lf",&x,&y);
}
inline Point operator-(const Point &b)const
{
return Point(x - b.x,y - b.y);
}
inline Point operator+(const Point &b)const
{
return Point(x + b.x,y + b.y);
}
inline Point operator*(const double &b)const
{
return Point(x * b,y * b);
}
inline double dot(const Point &b)const
{
return x * b.x + y * b.y;
}
inline double cross(const Point &b,const Point &c)const
{
return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y);
}
inline double Dis(const Point &b)const
{
return sqrt((*this-b).dot(*this-b));
}
inline bool InLine(const Point &b,const Point &c)const //三点共线
{
return !dcmp(cross(b,c));
}
inline bool OnSeg(const Point &b,const Point &c)const //点在线段上，包括端点
{
return InLine(b,c) && (*this - c).dot(*this - b) < eps;
}
int operator^(const Point &b) const
{
return y*b.x-x*b.y;
}
};
inline double min(double a,double b)
{
return a < b ? a : b;
}
inline double max(double a,double b)
{
return a > b ? a : b;
}
inline double Sqr(double x)
{
return x * x;
}
inline double Sqr(const Point &p)
{
return p.dot(p);
}
Point LineCross(const Point &a,const Point &b,const Point &c,const Point &d)
{
double u = a.cross(b,c), v = b.cross(a,d);
return Point((c.x * v + d.x * u) / (u + v), (c.y * v + d.y * u) / (u + v));
}
double LineCrossCircle(const Point &a,const Point &b,const Point &r,
double R,Point &p1,Point & p2)
{
Point fp = LineCross(r, Point(r.x+a.y-b.y, r.y+b.x-a.x), a, b);
double rtol = r.Dis(fp);
double rtos = fp.OnSeg(a, b) ? rtol : min(r.Dis(a), r.Dis(b));
double atob = a.Dis(b);
double fptoe = sqrt(R * R - rtol * rtol) / atob;
if( rtos > R - eps ) return rtos;
p1 = fp + (a - b) * fptoe;
p2 = fp + (b - a) * fptoe;
return rtos;
}
double SectorArea(const Point &r,const Point &a,const Point &b,double R) //不大于180度扇形面积，r->a->b逆时针
{
double A2 = Sqr(r - a), B2 = Sqr(r - b), C2 = Sqr(a - b);
return R * R * acos( (A2 + B2 - C2) * 0.5 / sqrt(A2) / sqrt(B2)) * 0.5;
}
double TACIA(const Point &r,const Point &a,const Point &b,double R)
{
double adis = r.Dis(a), bdis = r.Dis(b);
if( adis < R + eps && bdis < R + eps )
return r.cross(a, b) * 0.5;
Point ta, tb;
if( r.InLine(a,b) ) return 0.0;
double rtos = LineCrossCircle(a, b, r, R, ta, tb);
if( rtos > R - eps )
return SectorArea(r, a, b, R);
if( adis < R + eps )
return r.cross(a, tb) * 0.5 + SectorArea(r, tb, b, R);
if( bdis < R + eps )
return r.cross(ta, b) * 0.5 + SectorArea(r, a, ta, R);
return r.cross(ta, tb) * 0.5 + SectorArea(r, tb, b, R) + SectorArea(r, a, ta, R);
}
const int MAXN = 505;
Point p[MAXN];
double SPICA(int n,Point r,double R)
{
int i;
double ret = 0, if_clock_t;
for( i = 0 ; i < n ; ++i )
{
if_clock_t = dcmp(r.cross(p[i], p[(i + 1) % n]));
if( if_clock_t < 0 )
ret -= TACIA(r, p[(i + 1) % n], p[i], R);
else ret += TACIA(r, p[i], p[(i + 1) % n], R);
}
return fabs(ret);
}
double ComputePolygonArea(int n)
{
double sum=0;
for(int i=1;i<=n-1;i++)
sum+=(p[i]^p[i-1]);
sum+=(p[0]^p[n-1]);
return fabs(sum/2);
}
int main()
{
int n,m;
scanf("%d",&n);///多边形n个顶点
for(int i = 0 ; i < n ; ++i )///顶点坐标
p[i].input();
double polyArea = ComputePolygonArea(n);///计算多边形面积
scanf("%d",&m);
while(m--)
{
Point circle;
circle.input(); ///圆心坐标
int pp,qq;
scanf("%d%d",&pp,&qq);
double area = (1.0-(double)pp/qq)*polyArea;
///二分圆的半径
// printf("%f\n",area);
double l =0, r=1e18;
///固定二分次数
for(int i=1;i<300;i++){
double mid = (l+r)/2.0;
double insection = SPICA(n,circle,mid); ///圆与多边形交的面积
if(insection>area){
r = mid-eps;
}else{
l = mid;
}
}
printf("%.10lf\n",r);
}
return 0;
}