第九届河南理工大学算法程序设计竞赛

人外有人,外校的强者还是多。

A.Asia区域赛

感谢组委会给我们学校举办区域赛的机会!

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int maxn=1000000+10;
int main()
{
printf("%d",29+58+87+11+1+1);
return 0;
}

B.Asia区域制

二进制转16进制,四位二进制相当于一位16进制,直接按照定义模拟就可以了。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int maxn=1000000+10;
char str[1000000+100];
char num[100]="0123456789abcdef";
void cal(int pos){
int res=0;
if(pos<=0){
for(int i=0;i<pos+4;i++){
res=res*2+(str[i]-'0');
}
printf("%c",num[res]);
return;
}
cal(pos-4);
res=0;
for(int i=pos;i<pos+4;i++){
res=res*2+(str[i]-'0');
}
printf("%c",num[res]);
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%s",str);
int len=strlen(str);
cal(len-4);
printf("\n");
}
return 0;
}

C.Asia区域宫

题目有句话很重要:障碍物在迷宫中不能同行且不能同列,因此只要不是从左下角连到右上角(不一定非得是角落)把地图分成两份,那么就可以走到,并且不用走多余的步数。

所以我们只要统计每一斜线上的格子是否被填满,当 x1+y1=x2+y2时,这两个格子在同一斜线。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int maxn=1000000+10;
#define pi pair<int,int>
int a[maxn];
int main()
{
int t,x,y,n,m;
scanf("%d",&t);
while(t--){
memset(a,0,sizeof(a));
scanf("%d %d",&n,&m);
int flag=0;
while(m--){
scanf("%d %d",&x,&y);
x--,y--;
a[n+x+y]++;
if(x+y<n){
if( a[n+x+y] == x+y+1 ) flag=1;
}
else{
if(a[n+x+y]==n*2-1-x-y) flag=1;
}
}
if(flag==0) printf("Yes %d\n",n*2-2);
else printf("No\n");
}
return 0;
}

D.Asia区域阵

确认过眼神,不是我的题。

这个题数据范围不大,但是复杂度较高。

我们枚举所有的起点(异矩阵的左上角),然后枚举异矩阵的行列大小。然后就可以慢慢求解。

我们在枚举异矩阵的列的时候,如果遇到了重复的字符,那么就直接结束,并且此时我们知道了列的最大值,因此我们可以更新列的范围。(当时应该就是因为这个超时了)

对于 6 * 6 的矩阵

如果(红色为选中的异矩阵,黑色为重复字符):

那么我们接下来最多就只能进行到:

列数是越来越小,不可能比之前的还大了。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int maxn=1000000+10;
char str[1000][1000];
int main()
{
int t,n,m;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
scanf("%s",str[i]);
}
int res=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
map<char,int>mpl[30],mpr[30];
int length=26;
for(int k=0;k<26,k+i<n;k++){
for(int l=0;l<length;l++){
if( mpl[k][ str[i+k][j+l] ] > 0 || mpr[l][ str[i+k][j+l] ] > 0){
length=min(length,l);//减小length的范围
break;
}
mpl[k][ str[i+k][j+l] ]++;
mpr[l][ str[i+k][j+l] ]++;
res=max(res,(k+1)*(l+1));
}
}
}
}
printf("%d\n",res);
}
return 0;
}

E.Mo的游戏

也是模拟,注意一下每个字符第一次出现的情况就行了。

保存这个字符上一次出现的位置,然后根据现在这个位置和保存的上个位置的差值来进行求解。如果之前没有出现过这个字符,那么就跳过,不用计算。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int maxn=1000000+10;
char str[1000000];
int pos[100000];
int res[100000];
int main()
{
memset(pos,-1,sizeof(pos));
memset(res,INF,sizeof(res));
scanf("%s",str);
int len=strlen(str);
map<char,int>mp;
for(int i=0;i<len;i++){
mp[str[i]]++;
if(pos[str[i]]>=0){
res[str[i]]=min(i-pos[str[i]],res[str[i]]);
}
pos[str[i]]=i;
}
for(char i='a';i<='z';i++){
if(mp[i]){
printf("%c:",i);
if(res[i]!=INF) printf("%d",len-res[i]);
else printf("0");
printf("\n");
}
}
for(char i='A';i<='Z';i++){
if(mp[i]){
printf("%c:",i);
if(res[i]!=INF) printf("%d",len-res[i]);
else printf("0");
printf("\n");
}
}
return 0;
}

F.Mo的极限

炒鸡大模拟,简直了。。。

因为多项式的格式为 kx^y ,所以我们找 k 和 y 时可以直接根据它们的相对位置来求解。

首先当然是确认k的正负,根据 k 前面的 + - 字符判断,然后再运算符之后就是 k 的值。

计算出 k 的值之后,k 和 y 之间相差了一个 x^ 因此把位置向后挪两位,就可以直接开始求 y 的值。

坑1:每个项可能会抵消,所以要用数组存每个项的系数。

坑2:最后输出不能有1/-2这种情况,必须是-1/2。(我因为这个多wa了两次QAQ)

坑3:应该是没其他太大的坑了。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int maxn=1000000+10;
char str1[maxn],str2[maxn];
int xishu1[maxn],xishu2[maxn];
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}
int main()
{
int sum,x,y,flag;
int max_xishu1=-1,max_xishu2=-1;
int max_mi1=-1,max_mi2=-1;
scanf("%s %s",str1,str2);
int len1=strlen(str1);
sum=0;
x=y=0;
flag=1;
for(int i=0;i<len1;i++){
if(str1[i]=='-') flag=-1,i++;
else if(str1[i]=='+') flag=1,i++;
if(str1[i]>='0' && str1[i]<='9'){
while(str1[i]>='0' && str1[i]<='9'){
x=x*10+str1[i]-'0';
i++;
}
x*=flag;
i+=2;
}
if(str1[i-1]=='^' && str1[i]>='0' && str1[i]<='9'){
while(str1[i]>='0' && str1[i]<='9'){
y=y*10+str1[i]-'0';
i++;
}
xishu1[y]+=x;
}
x=0,y=0;
if(i>=len1-1) break;
i--;
}
for(int i=10000;i>=0;i--){
if(xishu1[i]){
max_mi1=i;
max_xishu1=xishu1[i];
break;
}
}
int len2=strlen(str2);
sum=0;
x=y=0;
flag=1;
for(int i=0;i<len2;i++){
if(str2[i]=='-') flag=-1,i++;
else if(str2[i]=='+') flag=1,i++;
if(str2[i]>='0' && str2[i]<='9'){
while(str2[i]>='0' && str2[i]<='9'){
x=x*10+str2[i]-'0';
i++;
}
x*=flag;
i+=2;
}
if(str2[i-1]=='^' && str2[i]>='0' && str2[i]<='9'){
while(str2[i]>='0' && str2[i]<='9'){
y=y*10+str2[i]-'0';
i++;
}
xishu2[y]+=x;
}
x=0,y=0;
if(i>=len2-1) break;
i--;
}
for(int i=10000;i>=0;i--){
if(xishu2[i]){
max_mi2=i;
max_xishu2=xishu2[i];
break;
}
}
if(max_mi1==-1) printf("0");
else if(max_mi1>max_mi2) printf("oo\n");
else if(max_mi1<max_mi2) printf("0\n");
else{
if(max_xishu1%max_xishu2==0){
printf("%d\n",max_xishu1/max_xishu2);
}
else{
int g=gcd(max_xishu1,max_xishu2);
if(max_xishu2/g<0){
max_xishu1*=-1;
max_xishu2*=-1;
}
printf("%d/%d",max_xishu1/g,max_xishu2/g);
}
}
return 0;
}

G.Mo的数学

容斥定理+逆元。

这个如果直接用循环就会超时。

我们先预处理 1 ~ n 的阶乘,可以省下不少时间。

思路是:找出 n ! (n的阶乘),然后除以不符合条件的数(不互质的数)。

然后我们对 m 的因子进行处理,可以知道的是,如果m的质因子 a ,那么 a * x(x>=0) 必然与 m 不互质,而且在 [ 1 , n ] 的范围内 a 的倍数相乘结果为$ f(a)=a^{n/a}*(n/a)! $ ,因为区间内 a 的倍数只有 n / a 个,然后就是容斥定理(容斥定理详见我之前的博客(算数基本定理+容斥定理))。

但是在除以 f(a) 时,可能会出现除不尽的情况,因此需要用逆元来处理一下。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int maxn=1000000+10;
const ll mod=1000000000+7;
ll mul[maxn];
ll yinzi[maxn];
void init()
{
mul[1]=1;
for(ll i=2;i<maxn;i++){
mul[i]=mul[i-1]*i%mod;
}
}
ll mulpow(ll x,ll b){
ll res=1;
while(b){
if(b&1) res=res*x%mod;
x=x*x%mod;
b>>=1;
}
return res;
}
int main()
{
init();
ll n,m,i,j;
ll res,sum,s,x;
while(~scanf("%lld %lld",&n,&m)){
res=mul[n];
sum=0;
for(i=2;i*i<=m;i++){
if(m%i==0){
yinzi[sum++]=i;
while(m%i==0) m/=i;
}
}
if(m!=1) yinzi[sum++]=m;
for(i=1;i<=(1<<sum)-1;i++){
x=1;
s=0;
for(j=0;j<sum;j++){
if((i>>j)&1){
s++;
x*=yinzi[j];
}
}
if(x>n) continue;
if(s&1){
res=res*mulpow(mulpow(x,n/x),mod-2)%mod;
res=res*mulpow(mul[n/x],mod-2)%mod;
}
else{
res=res*mulpow(x,n/x)%mod;
res=res*mul[n/x]%mod;
}
}
printf("%lld\n",res%mod);
}
return 0;
}

H.Mo的面积

做了第三遍了…详见之前的博客矩阵面积并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
const int maxn=1000000+10;
int main()
{
int a[100];
for(int i=1;i<=8;i++){
scanf("%d",&a[i]);
}
int r=min(max(a[1],a[3]),max(a[5],a[7]));
int l=max(min(a[1],a[3]),min(a[5],a[7]));

int u=min(max(a[2],a[4]),max(a[6],a[8]));
int d=max(min(a[2],a[4]),min(a[6],a[8]));
int bing;
if(r-l<0 || u-d<0) bing=0;
else bing=(r-l)*(u-d);
printf("%d\n",(a[3]-a[1])*(a[4]-a[2])+(a[7]-a[5])*(a[8]-a[6])-bing);
return 0;
}

I.安全距离

防AK题果然毒瘤。

二分适用于单调性的区间,由于这个题目球面是个弧线,并不是直线,因此需要用三分来求解。

然后我们就用三分的思想来求解。

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
#include <bits/stdc++.h>

using namespace std;

struct P {
double x, y, z;
P() {}
P(double _x, double _y, double _z) {
x = _x;
y = _y;
z = _z;
}
double operator*(const P &b) const { return x * b.x + y * b.y + z * b.z; }
P operator*(const double &b) const { return P(x * b, y * b, z * b); }
P operator-(const P &b) const { return P(x - b.x, y - b.y, z - b.z); }
P operator+(const P &b) const { return P(x + b.x, y + b.y, z + b.z); }
double dis(const P &b) const { return sqrt((*this - b) * (*this - b)); }
};

inline double f(const P &a, const P &b, const P &o, const double &t) {
P p = a + ((b - a) * t);
return p.dis(o);
}
inline double g(const P &s, const P &t, const P &o) {
double low = 0.0, top = 1.0;
for (int i = 0; i < 80; ++i) {
double m = (top - low) / 3.0;
double l = low + m;
double r = top - m;
if (f(s, t, o, l) >= f(s, t, o, r))
low = l;
else
top = r;
}
return f(s, t, o, low);
}

double DIS(P s, P b, P c, P o) {
double low = 0.0, top = 1.0;
for (int i = 0; i < 80; ++i) {
double m = (top - low) / 3;
double l = low + m;
double r = top - m;
if (g(s, b + (c - b) * l, o) >= g(s, b + (c - b) * r, o))
low = l;
else
top = r;
}
return g(s, b + ((c - b) * low), o);
}

int main() {
std::ios::sync_with_stdio(false);
P s, b, c, o;
double r;
int n;
cin >> n;
while (n--) {
cin >> s.x >> s.y >> s.z >> b.x >> b.y >> b.z >> c.x >> c.y >> c.z >> o.x >> o.y >>
o.z >> r;
double dis = min(min(DIS(b, s, c, o), DIS(s, b, c, o)), DIS(c, s, b, o));
printf("%.6lf\n", max(0.0, dis - r));
}
return 0;
}

J.简单递归

直接抄就完事了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
const int maxn=1000000+10;
ll res[maxn];
void init(){
res[0]=res[1]=res[2]=1;
for(int i=3;i<maxn;i++){
res[i]=((res[i-1]<<1)%mod+(res[i-2]>>1)%mod)%mod;
}
}
int main()
{
init();
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%lld\n",res[n]);
}
return 0;
}

K.高度期望

贪心一发,能多加尽量多加。

选取尽量低的树,这样加的高度就更多。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int maxn=1000000+10;
int a[maxn];
int main()
{
int n,m;
scanf("%d %d",&n,&m);
int sum=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
sort(a,a+n);
int res=0;
for(int i;i<n;i++){
if(sum>=m*n) break;
else{
res++;
sum+=(1000-a[i]);
}
}
printf("%d\n",res);

return 0;
}

L.最优规划

最小生成树裸题。

前m个路径长度不用管,直接把城镇相连。

之后s个用结构体保存,排序之后选择,然后并查集莽一发就过了。

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
#include<stdio.h>
#include<algorithm>
using namespace std;
int father[100010];
struct node{
int x,y;
int val;
}qwe[100010];
bool cmp(node c,node d)
{
return c.val<d.val;
}
int find(int c)
{
return father[c]==c?c:father[c]=find(father[c]);
}
int join(int c,int d)
{
int x1=find(c);
int x2=find(d);
if(x1!=x2)
{
father[x2]=x1;
return 1;
}
return 0;
}
int main()
{

int n,m,s;
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n;i++) father[i]=i;
for(int i=0;i<m;i++)
{
int a,b,val;
scanf("%d%d%d",&a,&b,&val);
join(a,b);

}
for(int i=0;i<s;i++)
{
scanf("%d%d%d",&qwe[i].x,&qwe[i].y,&qwe[i].val);
}
sort(qwe,qwe+s,cmp);
long long sum=0;
for(int i=0;i<s;i++)
{
if(join(qwe[i].x,qwe[i].y))
{
sum+=qwe[i].val;
}
}
int t=0;
for(int i=1;i<=n;i++)
{
if(father[i]!=i) t++;
}
if(t==n-1)
{
printf("%lld\n",sum);
}
else printf("Concubines can't do it.\n");
return 0;
}

还是把代码贴上吧。

代码太丑,仅供参考。

感谢您的支持
-------------本文结束感谢您的阅读-------------