福建2017省赛

自用笔记算法

福建2017省赛

A

题目要求

鸡兔同笼

参考AC代码

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
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		cout<<(m-2*n)/2<<" "<<(4*n-m)/2<<endl;
	}
	return 0;
}

思路

列方程推出一般表达式

B

题目要求

给出2个三角形三个顶点 共6个坐标 判断2个三角形是相交 还是包含 还是相离的关系
注意重合也算相交

参考AC代码

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<map>
#include<stack>
#include<set>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define zero(x)(((x)>0?(x):-(x))<eps)
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
const int maxisn=10;
int dcmp(double x){
    if(x>eps) return 1;
    return x<-eps ? -1 : 0;
}
inline double Sqr(double x){
    return x*x;
}
struct Point{
    double x,y;
    Point(){x=y=0;}
    Point(double x,double y):x(x),y(y){};
    friend Point operator + (const Point &a,const Point &b) {
        return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
        return Point(a.x-b.x,a.y-b.y);
    }
    friend bool operator == (const Point &a,const Point &b) {
        return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
    }
    friend Point operator * (const Point &a,const double &b) {
        return Point(a.x*b,a.y*b);
    }
    friend Point operator * (const double &a,const Point &b) {
        return Point(a*b.x,a*b.y);
    }
    friend Point operator / (const Point &a,const double &b) {
        return Point(a.x/b,a.y/b);
    }
    friend bool operator < (const Point &a, const Point &b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    }
    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);
    }
};
Point a[222],b[222];
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 PolygonArea(Point p[],int n){
     if(n<3) return 0.0;
     double s=p[0].y*(p[n-1].x-p[1].x);
     p[n]=p[0];
     for(int i=1;i<n;i++){
        s+=p[i].y*(p[i-1].x-p[i+1].x);
     }
     return fabs(s*0.5);
}
double CPIA(Point a[],Point b[],int na,int nb){
    Point p[maxisn],temp[maxisn];
    int i,j,tn,sflag,eflag;
    a[na]=a[0],b[nb]=b[0];
    memcpy(p,b,sizeof(Point)*(nb+1));
    for(i=0;i<na&&nb>2;++i){
        sflag=dcmp(a[i].cross(a[i+1],p[0]));
        for(j=tn=0;j<nb;++j,sflag=eflag){
            if(sflag>=0) temp[tn++]=p[j];
            eflag=dcmp(a[i].cross(a[i+1],p[j+1]));
            if((sflag^eflag)==-2)
                temp[tn++]=LineCross(a[i],a[i+1],p[j],p[j+1]);
        }
        memcpy(p,temp,sizeof(Point)*tn);
        nb=tn,p[nb]=p[0];
    }
    if(nb<3) return 0.0;
    return PolygonArea(p,nb);
}
double SPIA(Point a[],Point b[],int na,int nb){
    int i,j;
    Point t1[4],t2[4];
    double res=0.0,if_clock_t1,if_clock_t2;
    a[na]=t1[0]=a[0];
    b[nb]=t2[0]=b[0];
    for(i=2;i<na;i++){
        t1[1]=a[i-1],t1[2]=a[i];
        if_clock_t1=dcmp(t1[0].cross(t1[1],t1[2]));
        if(if_clock_t1<0) swap(t1[1],t1[2]);
        for(j=2;j<nb;j++){
            t2[1]=b[j-1],t2[2]=b[j];
            if_clock_t2=dcmp(t2[0].cross(t2[1],t2[2]));
            if(if_clock_t2<0) swap(t2[1],t2[2]);
            res+=CPIA(t1,t2,3,3)*if_clock_t1*if_clock_t2;
        }
    }
    return res;
}
double length(Point p1,Point p2){
    double res=sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
    return res;
}
double area_triangle(double l1,double l2,double l3){
    double s=(l1+l2+l3)/2.0;
    double res=sqrt(s*(s-l1)*(s-l2)*(s-l3));
    return res;
}
double xmult(Point p1,Point p2,Point p0){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int parallel(Point u1,Point u2,Point v1,Point v2){
    return zero((u1.x-u2.x)*(v1.y-v2.y)-(v1.x-v2.x)*(u1.y-u2.y));
}
int dot_online_in(Point p,Point l1,Point l2){
    return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		for(int i=0;i<3;i++) cin>>a[i].x>>a[i].y;
		for(int i=0;i<3;i++) cin>>b[i].x>>b[i].y;
		double area=fabs(SPIA(a,b,3,3));
		double l1=length(a[0],a[1]),l2=length(a[0],a[2]),l3=length(a[1],a[2]);
		double l4=length(b[0],b[1]),l5=length(b[0],b[2]),l6=length(b[1],b[2]);
		if(area>eps){
			if(abs(area-area_triangle(l1,l2,l3))<eps) cout<<"contain"<<endl;
			else if(abs(area-area_triangle(l4,l5,l6))<eps) cout<<"contain"<<endl;
			else cout<<"intersect"<<endl;
		}
		else{
			bool flag=false;
			for(int i=0;i<2;i++){
				for(int ii=i+1;ii<3;ii++){
					for(int j=0;j<3;j++){
						if(dot_online_in(b[j],a[i],a[ii])){
							flag=true;
							break;
						}
					}
					if(flag) break;
				}
				if(flag) break;
			}
			if(flag) cout<<"intersect"<<endl;
			else cout<<"disjoint"<<endl;
		}
	}
	return 0;
}

思路

使用多边形面积交的模版
先判断2个三角形有没有相交的面积 如果有 判断是相交还是包含
如果相交面积等于任意一个三角形的面积 那么为包含 否则为相离
如果没有相交的面积 判断是相离还是相交 如果三角形b的任意一个顶点在三角形a的任意一条边上 为相交
否则为相离
注意模版中的判0操作均为eps

D

题目要求

A和B各有一个数字
每次可以进行2个操作 翻转操作和/10操作 注意0/0=0
如果两者数字可以相等 A赢 否则B赢

参考AC代码

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
72
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 1000050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
char a[maxn],b[maxn];
int nextl[maxn];
int lena,lenb;
void getnext(){
	nextl[0]=-1;
	for(int i=1;i<lenb;i++){
		int j=nextl[i-1];
		while(b[j+1]!=b[i] && j>-1) j=nextl[j];
		nextl[i]=(b[j+1]==b[i])?j+1:-1;
	}
}
int kmp(char *a,char *b){
	getnext();
	int sum=0,i=0,j=0;
	while(i<lena && j<lenb){
		if(j==-1 || a[i]==b[j]) i++,j++;
		else j=nextl[j];
	}
	if(j==lenb) return 1;
	return 0;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>a>>b;
		lena=strlen(a),lenb=strlen(b);
		if(lena<lenb){
			cout<<"Bob"<<endl;
			continue;
		}
		if(lenb==1 && b[0]=='0'){
			cout<<"Alice"<<endl;
			continue;
		}
		if(kmp(a,b)){
			cout<<"Alice"<<endl;
			continue;
		}
		reverse(b,b+lenb);
		if(kmp(a,b)){
			cout<<"Alice"<<endl;
			continue;
		}
		cout<<"Bob"<<endl;
	}
	return 0;
}

题目要求

kmp
如果A的长度小于B B赢
如果B等于0 A赢
否则判断A是否匹配B和B的逆串 匹配则A赢

F

题目要求

题意: 给定一棵根为1, n个结点的树. 有q个操作,有两种不同的操作
(1) 1 v k x : a[v] += x, a[v’] += x – k, a[v ’’] += x – 2 * k … ;
v’为v的儿子 v ’’是v ’的儿子
(2) 2 v : 输出a[v] % (1e9 + 7);

参考AC代码

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
72
73
74
75
76
77
78
79
80
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#define maxn 300050
#define pb  push_back  
#define mm(a,b) memset(a,b,sizeof(a))
#define LL long long
using namespace std;  
const LL mod = 1e9+7;  
vector<int> e[maxn];   
LL x,k;  
int n;
int step;  
int in[maxn],out[maxn];
int dep[maxn];
LL tree1[maxn],tree2[maxn];  
void change(LL *tree,int x,LL val){
    while(x<=n) {
        tree[x]+=val;
        x+=x&(-x);
    }
}
LL sum(LL *tree,int x){
    LL res=0;
    while (x){
        res+=tree[x];
        x-=x&(-x);
    }
    return res;
}
void dfs(int u,int fa,int depth){  
    in[u]=step++,dep[u]=depth;  
    for(int i=0;i<e[u].size();i++){  
        int v = e[u][i];  
        if(v==fa) continue;  
        dfs(v,u,depth+1);  
    }  
    out[u]=step;  
}  
int main(){  
//	freopen("input.txt","r",stdin);
    int t;  
    scanf("%d",&t);  
    while(t--){
        scanf("%d",&n);  
        step=1;  
        for(int i = 0; i<=n; i++) e[i].clear();  
        for(int i = 2; i<=n; i++){
            int p; scanf("%d",&p);  
            e[p].push_back(i);  
        }  
        dfs(1,0,0);  
        int q; scanf("%d",&q);   
        mm(tree1,0),mm(tree2,0);
        while(q--){
        	int type;
            scanf("%d",&type);  
            if(type==1){  
            	int v;
				scanf("%d%lld%lld",&v,&x,&k);
                LL A=(x+k*dep[v])%mod;  
                change(tree1,in[v],A);  
                change(tree1,out[v],-A);   
                change(tree2,in[v],k);  
                change(tree2,out[v],-k);  
            }  
            else{
            	int v;
                scanf("%d",&v);   
                LL A = sum(tree1,in[v]);  
                LL B = sum(tree2,in[v]);  
                LL ans=((A-B*dep[v])%mod+mod)%mod;  
                printf("%lld\n",ans);
            }  
        }  
    }  
    return 0;  
}

思路

例如选定一棵以u节点为根节点的子树，v是这棵子树上的点。用dep[]数组来维护每个节点的深度。
那么一次更新操作相当于对 a[v] += x + (d[u] - d[v])k 整理得 a[v] += (x + kd[u] )- k*d[v] 括号部分对这个子树上的所有顶点是一个定值，
可以用线段树或者树状数组维护。而后一部分的d[v]是每个节点的深度属性，无需维护，所以我们只需要再开一个树状数组/线段树来维护k的和。
通过对这两个量的维护我们就可以针对每一个询问得到想要的结果。

本文标题:福建2017省赛

文章作者:Hippopmonkey

发布时间:2017-07-26, 22:30:22

最后更新:2017-09-28, 16:35:51

原始链接:http://xuboming8.github.io/2017/07/26/福建2017省赛/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 福建2017省赛
    1. 1.1. A
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. B
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. D
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 题目要求
    4. 1.4. F
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
|