A.貓貓與廣告
題目：
分析：
只需考慮c * d的矩陣豎著擺和橫著擺兩種情況，本題提示了考慮兩矩陣對應邊平行的情況，實際上可以證明倘若能斜著放，那么一定可以橫著放或豎著放，證明方式可已通過構造三角形來證明a* b的矩陣的長寬一定小于c * d矩陣的長寬，
code:
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int a, b, c, d;
cin >> a >> b >> c >> d;
if (a > b) swap(a, b);
if (c > d) swap(c, d);
if ((a <= c && b <= d) || (a <= d && b <= c))
cout << "YES";
else
cout << "NO";
return 0;
}
B.貓貓與密信
題目：
分析：
由于只消失一個字符，因此可以對可能存在love的子串進行討論：
①消失的不是字符i,則滿足條件的子串有：lve,loe,lov
②消失的字符是i，則滿足條件的子串只有：ove
所以從前往后列舉每一個字符，若其為i或者o則截取以其開頭的長度為3的子串，看是否滿足要求即可，
code:
#include <bits/stdc++.h>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
string s;
cin >> s;
bool flag = false;
for (int i = 0; i < s.size(); i ++)
{
if (s[i] == 'l')
{
string s2 = s.substr(i, 3);
if (s2 == "lve" || s2 == "loe" || s2 == "lov")
{
flag = true;
break;
}
}
else if (s[i] == 'o')
{
string s2 = s.substr(i, 3);
if (s2 == "ove")
{
flag = true;
break;
}
}
}
if (flag)
cout << "YES";
else
cout << "NO";
return 0;
}
C.貓貓與數列
題目：
分析：
這題的難點在處理溢位的問題，處理方式有很多，比如用long double或者int_128，這里介紹取對數的技巧，由于log(x)單調遞增，因此我們不妨對an取log，根據其log值來判斷大小關系，不過這里要處理精度的問題，我們可以讓an-1 * log(an-2)與log(2M)比，若an比2M都要大那自然大于M，否則我們再直接計算an并和M比較，這時就不用擔心溢位的問題，
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const double M = log(2e18);
const int N = 110;
LL a[N];
LL qmi(LL m, LL k)
{
LL res = 1, t = m;
while (k)
{
if (k & 1)
res = res * t;
t = t * t;
k >>= 1;
}
return res;
}
int main()
{
cin >> a[1] >> a[2];
int n = 3;
while(1)
{
if (a[n - 1] * log(a[n - 2]) > M)
{
n --;
break;
}
else
{
a[n] = qmi(a[n - 2], a[n - 1]);
if (a[n] > 1e18)
{
n --;
break;
}
n ++;
}
}
cout << n;
return 0;
}
D.貓貓與主人
題目：
分析：
每個元素有兩個維度的變數，考慮放到坐標系中去啟發思考，
我們用三角形表示小貓，圓形表示主人，我們可以發現對于每一個小貓，滿足條件的主人在其左上區域，因此我們不妨對小貓和主人按橫坐標排序，然后維護每一個小貓左上區域內的滿足條件的縱坐標值最大的主人，
code:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct Node
{
int a, b, idx;
}cat[N], p[N];
int ans[N];
bool cmp(Node A, Node B)
{
if (A.a != B.a)
return A.a < B.a;
else if (A.b != B.b)
return A.b < B.b;
else
return A.idx < B.idx;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i ++)
cin >> cat[i].a;
for (int i = 0; i < n; i ++)
{
cin >> cat[i].b;
cat[i].idx = i;
}
for (int i = 0; i < m; i ++)
cin >> p[i].b;
for (int i = 0; i < m; i ++)
{
cin >> p[i].a;
p[i].idx = i;
}
sort(cat, cat + n, cmp);
sort(p, p + m, cmp);
int Max = -0x3f3f3f3f;
for (int i = 0, j = 0; i < n; i ++)
{
while (j < m && p[j].a <= cat[i].a)
{
Max = max(Max, p[j].b);
j ++;
}
j --;
if (Max >= cat[i].b)
{
ans[cat[i].idx] = Max;
}
else
ans[cat[i].idx] = -1;
}
for (int i = 0; i < n; i ++)
cout << ans[i] << " ";
return 0;
}
E.貓貓與數學
題目：
分析：
①有解：
先考慮一般情況：由于兩邊都有c，因此需要轉化一下，不妨設a > b,根據更相減損法得gcd(a + c, b + c) = gcd(a - b, b + c) ≠ 1，列舉a - b得所有非1因數設為x，根據x反解c，然后對所有c的解取個min即為答案，
特判a - b = 0，若a = 1則c取1，否則c取0
②無解：
顯然當a - b = 1時無解，
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a, b, ans = 1e16;
void check(LL x)
{
if (x == 1)
return;
if (b % x == 0)
ans = min(ans, 0LL);
else
ans = min(ans, x - b % x);
}
int main()
{
cin >> a >> b;
if (a < b)
swap(a, b);
if (a - b == 1)
cout << -1;
else if (a == b)
{
if (a == 1)
cout << 1;
else
cout << 0;
}
else
{
LL d = a - b;
LL M = sqrt(d) + 1;
for (int i = 1; i <= M; i ++)
{
if (d % i == 0)
{
check(i);
check(d / i);
}
}
cout << ans;
}
return 0;
}
F.貓貓與寶石
題目：
分析：
推公式：
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 998244353, N = 2e5 + 5, M = (mod + 1) / 2;
LL a[N], b[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
LL n, s = 0;
cin >> n;
a[0] = b[0] = 1;
for (int i = 1; i <= n; i ++)
{
a[i] = a[i - 1] * 2 % mod;
b[i] = b[i - 1] * M % mod;
}
for (int i = 1; i <= n; i ++)
{
int x;
cin >> x;
s = (s + x) % mod;
cout << (((a[i - 1] + (a[i - 2] * (i - 1) % mod)) % mod) * s % mod) * b[i] % mod << " ";
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/551196.html
標籤：其他
上一篇：排序演算法之詳解冒泡排序
下一篇：返回列表