湖南大学2020届ACM新生赛 全部题解
新生赛过后，熬了4天夜，终于把模型机验收完了，还有一星期多期末考试，抽空写个题解。A Counting 0 and 1 in string0->11->101是由0，1转移过来，0是由1转移过来。因此列出状态转移的方程即可#include <iostream>using namespace std;long long f0[100], f1[100];int main(){
·
新生赛过后，熬了4天夜，终于把模型机验收完了，还有一星期多期末考试，抽空写个题解。
A Counting 0 and 1 in string
0->1 1->10
1是由0，1转移过来，0是由1转移过来。
因此列出状态转移的方程即可
#include <iostream>
using namespace std;
long long f0[100], f1[100];
int main()
{
f0[0] = 1, f1[0] = 1;
int t;
cin >> t;
for (int i = 1; i <= 50; i ++)
{
f0[i] = f1[i - 1];
f1[i] = f0[i - 1] + f1[i - 1];
}
while (t --)
{
int n;
cin >> n;
cout << f0[n - 1] << ' ' << f1[n - 1] <<endl;
}
return 0;
}
B Where is the billiard ball going?
考试的时候脑子坏掉了，写了三百多行的模拟还错了。
考后思考：小球的最后位置x，y是相互独立的，因此可以分别处理x的坐标和y的坐标。
小球的移动可看成光线的反射和直射。
例如对于处理x ： 可以先假设台球桌面是无限大的，因此算出t秒后球的位置，球的位置模上（x - 2r）或是t秒后球在桌面上的位置，或是球相对桌面的镜面反射。因此只需要判断球是在原本的位置上，还是在镜面反射的位置上即可。最后注意边界情况，如小球恰好停在边界上。
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
int main()
{
LL l, w, r, px, py, vx, vy, t;
int T;
cin >> T;
while (T --)
{
cin >> l >> w >> r >> px >> py >> vx >> vy >> t;
LL len = l - r - r;
px -= r;
px = px + t * vx;
int flag = (px >= 0) ? 1 : 0;
LL res = abs(px) / len;
px = (px % len + len) % len;
if ((res % 2 == 0 && flag) || (res % 2 == 1 && !flag))
{
if (flag || (!flag && px != 0))
px = px + r;
else
px = len + r;
}
else
{
if (flag || (!flag) && px != 0)
px = len - px + r;
else
px = r;
}
LL wid = w - r - r;
py -= r;
py = py + t * vy;
flag = (py >= 0) ? 1 : 0;
res = abs(py) / wid;
py = (py % wid + wid) % wid;
if ((res % 2 == 0 && flag) || (res % 2 == 1 && !flag))
{
if (flag || (!flag && py != 0))
py = py + r;
else
py = wid + r;
}
else
{
if (flag || (!flag) && py != 0)
py = wid - py + r;
else
py = r;
}
cout << px << ' ' << py << endl;
}
}
另一种思路：对于处理x，球的位置模上2（x - 2 * r），思路同上，但是少了一些边界情况的判断。
简单的贪心，能出剪刀时就尽量出剪刀，不能出剪刀时就出布。可以证得是最优方案。
#include <iostream>
using namespace std;
string s;
int t;
int main()
{
cin >> t;
while (t --)
{
int bu = 0, jiandao = 0, ans = 0;
int n;
cin >> n >> s;
for (int i = 0; i < n; i ++)
{
if (s[i] == 'P')
{
if (jiandao < bu)
{
jiandao ++;
ans ++;
}
else
{
bu ++;
}
}
else if (s[i] == 'S')
{
if (jiandao < bu)
{
jiandao ++;
}
else
{
bu ++;
ans --;
}
}
}
cout << ans <<endl;
}
return 0;
}
D Treasure cave
如果有一对数（2个）相等，则输出这个数。
如果有两对不同的数相等，则不能满足方案。
如果三个及以上的数相等，不能满足方案。
#include <iostream>
#include <algorithm>
const int N = 1e5 + 10;
int a[N];
using namespace std;
int main()
{
int t, x, n;
cin >> t;
while (t --)
{
int equals = 0, is_success = 1, num = 0;
cin >> n >> x;
for (int i = 0; i < n; i ++)
{
scanf("%d", &a[i]);
}
a[n] = x;
sort(a, a + n + 1);
for (int i = 0; i <= n; i ++)
{
if ( (i <= n - 1) && a[i] == a[i + 1])
{
equals ++;
num = a[i];
if (equals >= 2)
{
is_success = 0;
break;
}
}
if ((i <= n - 2) && a[i] == a[i + 1] && a[i] == a[i + 2])
{
is_success = 0;
break;
}
}
if (!is_success)
cout << 0 <<endl;
else
{
if (equals == 1)
cout << num << endl;
else
cout << a[n] <<endl;
}
}
return 0;
}
E Chicken and rabbit in the same cage
思路：搜索
因为k比较小，搜索k。
注意到：the starfish with fewer tentacles has higher value，因此注意搜索时的枚举顺序即可。
#include <iostream>
#include <algorithm>
using namespace std;
int t, n, m, k;
bool is_success = 0;
typedef long long LL;
int a[10];
int b[10];
struct spice
{
int cnt;
int bianhao;
bool operator < (spice W)
{
return cnt < W.cnt;
}
};
spice person[100];
void dfs(int step, int sum)
{
if (is_success)
return;
if (step == k)
{
a[k] = n - sum;
long long num = 0;
for (int i = 1; i <= k; i ++)
num += (LL)a[i] * person[i].cnt;
if (num == m)
{
for (int i = 1; i <= k; i ++) b[person[i].bianhao] = a[i];
for (int i = 1; i <= k; i ++) cout << b[i] << ' ';
cout << endl;
is_success = 1;
}
return;
}
for (int i = n - sum; i >= 0; i --)
{
a[step] = i;
dfs(step + 1, sum + i);
}
}
int main()
{
cin >> t;
int ss = 0;
while (t --)
{
is_success = 0;
cin >> n >> m >> k;
for (int i = 1; i <= k; i ++)
{
cin >> person[i].cnt;
person[i].bianhao = i;
}
sort(person + 1, person + k + 1);
dfs(1, 0);
if (!is_success)
cout << -1 << endl;
else
ss ++;
}
cout << ss;
return 0;
}
F forest
是这次比赛的防AK题（然而最多的人才做了7道，我好菜呀）
动态规划法
f[i][j][k] 表示前i棵树中，能看到j棵树，且其中最高的树高为k的需要的最小操作数。本题状态转移时从i -> i + 1，比较方便。
f[i + 1][j][max(a[i + 1], k)] = min(f[i][j][k]) （不选择a[i + 1]）
f[i + 1][j + 1][a[i + 1]] = min(f[i][j][k]) （a[i + 1]大于k时,选择a[i + 1]）
f[i + 1][j + 1][k + 1] = min(f[i][j][k] + k + 1 - a[i + 1]) （a[i + 1]小于等于k，选择a[i + 1])
#include <iostream>
#include <map>
using namespace std;
const int N = 110;
typedef long long LL;
map<int, LL> f[N][N];
int a[N];
#define x first
#define y second
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
f[0][0][0] = 0;
for (int i = 0; i <= n; i ++)
{
for (int j = 0; j <= n; j ++)
{
for (auto g: f[i][j])
{
int x = g.x;
int y = max(g.x, a[i + 1]);
if (!f[i + 1][j].count(y)) f[i + 1][j][y] = f[i][j][x];
else f[i + 1][j][y] = min(f[i + 1][j][y], f[i][j][x]);
if (a[i + 1] > x)
{
if (!f[i + 1][j + 1].count(a[i + 1])) f[i + 1][j + 1][a[i + 1]] = f[i][j][x];
else f[i + 1][j + 1][a[i + 1]] = min(f[i][j][x], f[i + 1][j + 1][a[i + 1]]);
}
else
{
int k = x + 1;
if (!f[i + 1][j + 1].count(k)) f[i + 1][j + 1][k] = f[i][j][x] + k - a[i + 1];
else f[i + 1][j + 1][k] = min(f[i + 1][j + 1][k], f[i][j][x] + k - a[i + 1]);
}
}
}
}
// for (int i = 0; i <= n; i ++)
// for (int j = 1; j <= n; j ++)
// {
// for (auto x: f[i][j])
// printf("--i%d--j%d--k%d--val%lld\n", i, j, x.first, x.second);
// }
// cout << f[1][1][0];
for (int j = 1; j <= n; j ++)
{
LL res = 1e18;
for (auto x: f[n][j])
{
res = min(res, x.second);
}
cout << res << ' ' ;
}
}
贪心法
期末考试后补
出题人rain_w ：还可以用并查集+线段树优化，使n可以到1e6。
搜索，for循环皆可
#include <iostream>
using namespace std;
int book[10];
int a[10];
void dfs(int step)
{
if (step == 10)
{
int num1 = 100 * a[1] + 10 * a[2] + a[3];
int num2 = 100 * a[4] + 10 * a[5] + a[6];
int num3 = 100 * a[7] + 10 * a[8] + a[9];
if (num1 + num2 + num3 == 999 && num1 < num2 && num2 < num3)
{
cout << num1 << ' ' <<num2 << ' ' <<num3 <<endl;
}
return;
}
for (int i = 1; i <= 9; i ++)
{
if (!book[i])
{
book[i] = 1;
a[step] = i;
dfs(step + 1);
book[i] = 0;
}
}
}
int main()
{
dfs(1);
return 0;
}
H Maximum subsegment product
简单的DP
f[i] 表示从1到i最大的乘积值
状态转移：f[i] = max(f[i], f[i - 1] * f[i]);
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
double f[N];
double maxn = 0;
int main()
{
f[0] = 1;
int n;
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> f[i];
}
for (int i = 1; i <= n; i ++)
{
f[i] = max(f[i], f[i - 1] * f[i]);
maxn = max(f[i], maxn);
}
printf("%.2lf", maxn);
return 0;
}
组合数问题。
m为序列长度，n为不超过的数
答案为C（m, m + n + 1）
比如说m=5，n=4
则序列44444 则表示(0, 1) -> (0, 4) -> (5, 4)
序列11111表示(0, 1)->(5, 1)->(5,4)
序列12344表示(0, 1)->(1, 1)->(1, 2)->(2, 2)->(2, 3)->(3, 3)->(3,4)->(4, 4)->(5,4)
求组合数通过求阶乘逆元/卢卡斯定理（之前博客不同范围求组合数）
#include <iostream>
#include <cstring>
using namespace std;
int n;
const int N = 2e6 + 10;
int fact[N]; //n的阶乘
int infact[N]; //n的阶乘的逆元
int MOD = 1e9 + 7;
typedef long long LL;
int qumi(int p, int k, int m) //快速幂
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * p % m;
p = (LL)p * p % m;
k >>= 1;
}
return res;
}
int main()
{
fact[0] = infact[0] = 1;
cin >> n;
for (int i = 1; i < N; i ++)
{
fact[i] = (LL)fact[i - 1] * i % MOD;
infact[i] = (LL)infact[i - 1] * qumi(i, MOD - 2, MOD) % MOD; // (a * b)^-1 和 (a ^ -1) * (b ^ -1) 同余
}
while (n --)
{
int a, b;
cin >> a >> b;
a = a + b - 1;
cout << (LL)fact[a] * infact[b] % MOD * infact[a - b] % MOD <<endl;
}
}
我不知道pell方程，是打表找规律做的，发现数不是完全平方数就满足规律。
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int T;
cin >> T;
while (T --)
{
int n;
cin >> n;
int ss = sqrt(n);
if (ss * ss == n)
cout << "no" <<endl;
else
cout << "yes" <<endl;
}
return 0;
}
K Sakuyalove Loves Games
出题人Sakuyalove：子弹的下降，相当于人的上升。因此只要人往左上，上，右上走不遇到子弹并且能走到顶部，就输出yes。
我的暴力做法：数组blt保存子弹的坐标，用数组st记录人的横向的坐标和当前所在时间。人每次走时，只要判断每个子弹是否落在人的身上决定能否走，当经过时间大于地图的纵向长度（n），就输出yes。
显然暴力做法复杂度大，每次操作需要判断每个子弹能否落在人身上。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
PII blt[N * N]; //子弹
int cnt;
char g[N][N];
int st[N][N]; // y坐标和t时间
int n, m;
PII person; //人的位置
#define x first
#define y second
PII q[N * N];
int tt, hh;
int dy[3] = {-1, 0, 1};
bool judge(int y, int t)
{
if (y <= 0 || y > m) return true;
if (st[y][t]) return true;
int x = person.x;
for (int i = 0; i < cnt; i ++)
{
if (t == x - blt[i].x && blt[i].y == y)
return true;
}
return false;
}
int main()
{
int T;
cin >> T;
while (T --)
{
memset(st, 0, sizeof st);
cnt = 0;
bool is_success = 0;
cin >> n >> m;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
cin >> g[i][j];
if (g[i][j] == 'S')
{
person.x = i, person.y = j;
// cout << "!!!";
}
else if (g[i][j] == 'O')
blt[cnt ++] = {i, j};
}
// printf("---%d--%d\n", person.x, person.y);
hh = tt = 0;
st[person.y][0] = 1;
q[0] = {person.y, 0};
while (hh <= tt)
{
auto p = q[hh ++];
int t = p.y;
if (t >= n)
{
is_success = 1;
cout << "yes" << endl;
break;
}
int y = p.x;
for (int i = 0; i < 3; i ++)
{
int ey = y + dy[i];
int et = t + 1;
if (judge(ey, et)) continue;
q[++ tt] = {ey, et};
st[ey][et] = 1;
}
}
if (!is_success)
{
cout << "no" << endl;
}
}
}
对于四个点x1, y1, x2, y2, x3, y3, x4, y4
可以分别求出x1, y1, x2, y2, x3, y3三个点中垂线的交点（X0, Y0）
x1, y1, x2, y2, x4, y3三个点中垂线的交点(X1, Y1)
（首先要判断不存在交点的情况，即两条直线平行）
如果交点重合，则在一个圆上，否则不在
需要先手写推出交点的坐标，然后代入公式即可
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const double eps = 1e-8;
double X0, Y0, X1, Y1;
double fun1(double x1, double y1, double x2, double y2, double x3, double y3, bool & p)
{
double m = (x3 - x1) * (y2 - y1) - (x2 - x1)*(y3 - y1);
if (fabs(m) < eps)
{
p = 0;
return -1;
}
return ((y3 - y2) * (y3 - y1) * (y2 - y1) + (x3 - x1) * (x3 + x1) * (y2 - y1) - (x2 - x1) * (x2 + x1) * (y3 - y1)) / 2 / m;
}
double fun2(double x1, double y1, double x2, double y2, double x3, double y3, double X)
{
if (fabs(y2 - y1) < eps)
return - (x3 - x1) * (X - (x1 + x3) / 2) / (y3 - y1) + (y1 + y3) / 2;
return - (x2 - x1) * (X - (x1 + x2) / 2) / (y2 - y1) + (y1 + y2) / 2;
}
int main()
{
double x1, y1, x2, y2, x3, y3, x4, y4;
int T;
cin >> T;
while (T --)
{
bool is_success = 1;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
X0 = fun1(x1, y1, x2, y2, x3, y3, is_success);
X1 = fun1(x1, y1, x2, y2, x4, y4, is_success);
if (is_success)
{
Y0 = fun2(x1, y1, x2, y2, x3, y3, X0);
Y1 = fun2(x1, y1, x2, y2, x4, y4, X1);
}
if (is_success == 1 && fabs(X0 - X1) < eps && fabs(Y0 - Y1) < eps)
cout << "yes" << endl;
else
cout << "no" << endl;
}
}
队友思路：
注意是凹四边形时的情况
根据定理，判断B,C在AD的同侧还是异侧，然后使用余弦定理，同侧则cosABD,cosACD相等，否则相反
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-10;
typedef pair<double,double> PII;
#define x first
#define y second
double len(PII p)
{
double res=sqrt(p.x*p.x+p.y*p.y);
//printf("%.2lf\n",res);
return res;
}
double len2(PII p)
{
double res=(p.x*p.x+p.y*p.y);
//printf("%.2lf\n",res);
return res;
}
double cha(PII p1,PII p2)
{
double res=p1.x*p2.y-p1.y*p2.x;
//printf("%2.lf\n",res);
return res;
}
int main()
{
int t;cin>>t;
while(t--)
{
PII A,B,C,D;
cin>>A.x>>A.y;
cin>>B.x>>B.y;
cin>>C.x>>C.y;
cin>>D.x>>D.y;
PII BA,BD,CA,CD, AD;
BA.x=A.x-B.x;BA.y=A.y-B.y;
BD.x=D.x-B.x;BD.y=D.y-B.y;
CA.x=A.x-C.x;CA.y=A.y-C.y;
CD.x=D.x-C.x;CD.y=D.y-C.y;
AD.x=D.x-A.x;AD.y=D.y-A.y;
/*if(cha(BA,BD)<eps||cha(CA,CD)<eps)
{
puts("no");
continue;
}*/
double s1=(len2(CD) + len2(CA) - len2(AD)) / 2/ len(CD) / len(CA);
double s2=(len2(BD) + len2(BA) - len2(AD)) / 2/ len(BD) / len(BA);
//printf("%.2lf\n%.2lf\n",o1,o2);
if(cha(BA,BD)*cha(CA,CD)>0&&fabs(s1-s2)<eps)
puts("yes");
else if(cha(BA,BD)*cha(CA,CD)<0&&fabs(s1+s2)<eps)
puts("yes");
else puts("no");
}
return 0;
}
惟楚有才，于斯为盛。欢迎来到长沙！！！ 茶颜悦色、臭豆腐、CSDN和你一个都不能少~
更多推荐
5
0- 0
已为社区贡献1条内容
所有评论(0)