新生賽過后,熬了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),思路同上,但是少了一些邊界情況的判斷,
C Scissors-Paper
簡單的貪心,能出剪刀時就盡量出剪刀,不能出剪刀時就出布,可以證得是最優方案,
#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,
G Lucky numbers
搜索,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;
}
I How many sequences?
組合數問題,
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;
}
}
J Sakuyalove Loves Math
我不知道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;
}
}
}
L Sakuyalove Loves Circles
對于四個點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;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/244372.html
標籤:其他
上一篇:哈夫曼樹實作電文編碼譯碼
下一篇:復試安排及常見問題
