目錄
- A
-
- Solution
- Code
- B
-
- Solution
- Code
- C
-
- Solution
- Code
- D
-
- Solution
- Code
- E
-
- Solution
- Code
- F
-
- Solution
- Code
- G
-
- Solution
- Code
- H
-
- Solution
- Code
- I
-
- Solution
- Code
- J
-
- Solution
- Code
A
Solution
按照題意,先切四次把二維碼切出來,然後看先切橫還是先切豎,取最小值。
但簡單證明可以得知,兩種方法答案都是443.
Code
/*************************************
* @file_name: A.cpp.
* @author: minamidesi
* @time: Insert Date/Time.
*************************************/
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define itn int
#define memmax 0x7fffffff
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define endl '\n'
const ll MOD = 1000000007;
const int intmax = 2147483647;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const ll ulmax = 4294967295ll;
// OUTPUT
template <class a, class b>
ostream &operator<<(ostream &os, const pair<a, b> &p)
{
os << "(" << p.first << " " << p.second << ")";
return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
os << "[";
if (!v.size())
os << "]";
else
for (int i = 0; i < v.size(); ++i)
os << v[i] << ",]"[i == v.size() - 1];
return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &s)
{
os << "{";
if (!s.size())
os << "}";
else
for (typename set<T>::iterator it = s.begin(); it != s.end(); it++)
os << *it << ",}"[*it == *s.rbegin()];
return os;
}
inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
inline void write(ll x)
{ //快寫
char F[200];
ll tmp = x > 0 ? x : -x;
if (x < 0)
putchar('-');
ll cnt = 0;
while (tmp > 0)
{
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0)
putchar(F[--cnt]);
}
ll a, b;
void solve()
{
a += 4;
a += 20-1;
a += (22-1)*20;
b += 4;
b += 22-1;
b += (20-1)*22;
// cout << "a = " << a << endl;
// cout << "b = " << b << endl;
// std::cout << "ans = ";
cout << min(a, b);
}
void run_code()
{
solve();
}
void run_code_with_time()
{
clock_t start, finish;
double totaltime;
start = clock();
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif// ONLINE_JUDGE
//================================================================
run_code();
//================================================================
#ifndef ONLINE_JUDGE
finish = clock();
totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
printf("\n此程式的運作時間為%.36lf秒!\n", totaltime);
#endif //ONLINE_JUDGE
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
run_code_with_time();
return 0;
}
B
Solution
推導一下,答案應該為
LLLV
Code
/*************************************
* @file_name: B.cpp.
* @author: minamidesi
* @time: Insert Date/Time.
*************************************/
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define itn int
#define memmax 0x7fffffff
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define endl '\n'
const ll MOD = 1000000007;
const int intmax = 2147483647;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const ll ulmax = 4294967295ll;
// OUTPUT
template <class a, class b>
ostream &operator<<(ostream &os, const pair<a, b> &p)
{
os << "(" << p.first << " " << p.second << ")";
return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
os << "[";
if (!v.size())
os << "]";
else
for (int i = 0; i < v.size(); ++i)
os << v[i] << ",]"[i == v.size() - 1];
return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &s)
{
os << "{";
if (!s.size())
os << "}";
else
for (typename set<T>::iterator it = s.begin(); it != s.end(); it++)
os << *it << ",}"[*it == *s.rbegin()];
return os;
}
inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
inline void write(ll x)
{ //快寫
char F[200];
ll tmp = x > 0 ? x : -x;
if (x < 0)
putchar('-');
ll cnt = 0;
while (tmp > 0)
{
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0)
putchar(F[--cnt]);
}
ll n;
void solve()
{
std::cout << "LLLV";
}
void run_code()
{
solve();
}
void run_code_with_time()
{
clock_t start, finish;
double totaltime;
start = clock();
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif// ONLINE_JUDGE
//================================================================
run_code();
//================================================================
#ifndef ONLINE_JUDGE
finish = clock();
totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
printf("\n此程式的運作時間為%.36lf秒!\n", totaltime);
#endif //ONLINE_JUDGE
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
run_code_with_time();
return 0;
}
C
Solution
用乘法結合律,不難看出 s = ∑ i = 1 n ∗ ∑ j = i + 1 n a j s=\sum_{i=1}^{n}*\sum_{j=i+1}^{n}a_j s=∑i=1n∗∑j=i+1naj
直接字首和a化簡為 O ( n ) O(n) O(n)算法即可。
Code
#include<bits/stdc++.h>
typedef long long ll;
ll n;
ll a[200005];
ll pre[200005];
void solve()
{
std::cin >> n;
for(int i=1; i<=n; i++)
{
std::cin >> a[i];
pre[i] = pre[i-1] + a[i];
}
ll res = 0;
for(int i=1; i<=n; i++)
{
res += a[i]*(pre[n]-pre[i]);
}
// std::cout << "ans = ";
std::cout << res;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif// ONLINE_JUDGE
// std::cin >> T;
// T=1;
// while(T--)
solve();
}
D
Solution
Code
E
Solution
DP做法:令
dp[i]
為結點i爬到樹頂的時間的期望值。
顯然,
dp[n] = 0
,即樹根爬到樹根的時間期望值為0.
Code
F
Solution
Code
G
Solution
大概就是 O ( n l o g n ) O(n\ log\ n) O(n log n)的LIS做法中,實時更新長度的最大值。
注意邊界情況。
具體看代碼。
Code
/*************************************
* @file_name: G.cpp.
* @author: minamidesi
* @time: Insert Date/Time.
*************************************/
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define itn int
#define memmax 0x7fffffff
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define endl '\n'
const ll MOD = 1000000007;
const int intmax = 2147483647;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const ll ulmax = 4294967295ll;
// OUTPUT
template <class a, class b>
ostream &operator<<(ostream &os, const pair<a, b> &p)
{
os << "(" << p.first << " " << p.second << ")";
return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
os << "[";
if (!v.size())
os << "]";
else
for (int i = 0; i < v.size(); ++i)
os << v[i] << ",]"[i == v.size() - 1];
return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &s)
{
os << "{";
if (!s.size())
os << "}";
else
for (typename set<T>::iterator it = s.begin(); it != s.end(); it++)
os << *it << ",}"[*it == *s.rbegin()];
return os;
}
inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
inline void write(ll x)
{ //快寫
char F[200];
ll tmp = x > 0 ? x : -x;
if (x < 0)
putchar('-');
ll cnt = 0;
while (tmp > 0)
{
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0)
putchar(F[--cnt]);
}
ll n, k;
ll a[100005];
ll b[100005];
ll res;
void solve()
{
std::cin >> n >> k;
for(int i=1; i<=n; i++)
{
std::cin >> a[i];
}
ll len = 0;
for(int i=1; i<=n; i++)
{
if(b[len] <= a[i])
{
b[++len] = a[i];
ll tmp = min(n, len+k);
res = max(res, tmp);
}
else
{
ll pt = upper_bound(b+1, b+len+1, a[i]) - b;
b[pt] = a[i];
ll tmp = min(n, pt+k);
res = max(res, tmp);
}
}
// std::cout << "ans = ";
std::cout << res;
}
void run_code()
{
solve();
}
void run_code_with_time()
{
clock_t start, finish;
double totaltime;
start = clock();
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif// ONLINE_JUDGE
//================================================================
run_code();
//================================================================
#ifndef ONLINE_JUDGE
finish = clock();
totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
printf("\n此程式的運作時間為%.36lf秒!\n", totaltime);
#endif //ONLINE_JUDGE
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
run_code_with_time();
return 0;
}
H
Solution
Code
I
Solution
顯然,如果這個數可以拆分成 x 1 y 1 ⋅ x 2 y 2 x_1^{y_1}·x_2^{y_2} x1y1⋅x2y2的形式,則這個數可以表達為 x 2 ⋅ y 3 x^2·y^3 x2⋅y3的形式。
嘗試枚舉 x 1 x_1 x1,看這個數除以 x 1 x_1 x1的平方後能不能開立方,或者除以 x 1 x_1 x1的立方後能不能開平方。
我們假設 x 1 < x 2 x_1<x_2 x1<x2,則枚舉到兩個數相同即可,複雜度為 O ( n 1 / 5 ) O(n^{1/5}) O(n1/5) ,1e18開五次方大概在4000左右,1s應該能過。
Code
/*************************************
* @file_name: I.cpp.
* @author: minamidesi
* @time: Insert Date/Time.
*************************************/
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define itn int
#define memmax 0x7fffffff
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define endl '\n'
const ll MOD = 1000000007;
const int intmax = 2147483647;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const ll ulmax = 4294967295ll;
// OUTPUT
template <class a, class b>
ostream &operator<<(ostream &os, const pair<a, b> &p)
{
os << "(" << p.first << " " << p.second << ")";
return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
os << "[";
if (!v.size())
os << "]";
else
for (int i = 0; i < v.size(); ++i)
os << v[i] << ",]"[i == v.size() - 1];
return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &s)
{
os << "{";
if (!s.size())
os << "}";
else
for (typename set<T>::iterator it = s.begin(); it != s.end(); it++)
os << *it << ",}"[*it == *s.rbegin()];
return os;
}
inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
inline void write(ll x)
{ //快寫
char F[200];
ll tmp = x > 0 ? x : -x;
if (x < 0)
putchar('-');
ll cnt = 0;
while (tmp > 0)
{
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0)
putchar(F[--cnt]);
}
ll T;
ll n;
void solve()
{
std::cin >> n;
// std::cout << "ans = ";
// 1e5 4e3 = 4e8
for(ll i = 1; i*i*i*i*i<=n; i++)
{
ll j = pow(n/i/i, 1.0/3);
if(n/i/i == j*j*j)
{
std::cout << "yes\n";
return ;
}
j = pow(n/i/i/i, 1.0/2);
if(n/i/i/i == j*j)
{
std::cout << "yes\n";
return ;
}
}
dp[i] = dp[i-1]
std::cout << "no\n";
}
void run_code()
{
// std::cout << "limit = " << pow(1e18, 0.2) << endl;
std::cin >> T;
for(int i=1; i<=T; i++)
solve();
}
void run_code_with_time()
{
clock_t start, finish;
double totaltime;
start = clock();
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif// ONLINE_JUDGE
//================================================================
run_code();
//================================================================
#ifndef ONLINE_JUDGE
finish = clock();
totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
printf("\n此程式的運作時間為%.36lf秒!\n", totaltime);
#endif //ONLINE_JUDGE
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
run_code_with_time();
return 0;
}
J
Solution
看了一眼覺得是差分限制,寫了個Dijkstra,但處理不了負邊,顯然不合理。。。
待修改。。
Code
/*************************************
* @file_name: J.cpp.
* @author: minamidesi
* @time: Insert Date/Time.
*************************************/
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define itn int
#define memmax 0x7fffffff
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define endl '\n'
const ll MOD = 1000000007;
const int intmax = 2147483647;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const ll ulmax = 4294967295ll;
// OUTPUT
template <class a, class b>
ostream &operator<<(ostream &os, const pair<a, b> &p)
{
os << "(" << p.first << " " << p.second << ")";
return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
os << "[";
if (!v.size())
os << "]";
else
for (int i = 0; i < v.size(); ++i)
os << v[i] << ",]"[i == v.size() - 1];
return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &s)
{
os << "{";
if (!s.size())
os << "}";
else
for (typename set<T>::iterator it = s.begin(); it != s.end(); it++)
os << *it << ",}"[*it == *s.rbegin()];
return os;
}
inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
inline void write(ll x)
{ //快寫
char F[200];
ll tmp = x > 0 ? x : -x;
if (x < 0)
putchar('-');
ll cnt = 0;
while (tmp > 0)
{
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0)
putchar(F[--cnt]);
}
ll n, m, q;
struct edge
{
ll next, to;
ll weight;
}edge[100005];
ll head[100005];
ll cnt;
void addedge(ll u, ll v, ll w)
{
cnt++;
edge[cnt].next = head[u];
head[u] = cnt;
edge[cnt].to = v;
edge[cnt].weight = w;
}
ll dis[100005];
bool used[100005];
struct node
{
ll pos;
ll dis;
node(ll a, ll b)
{
pos = a;
dis = b;
}
friend bool operator<(const node a, const node b )
{
return a.dis > b.dis;
}
};
void dijkstra(ll st)
{
for(int i=0; i<=n; i++)
dis[i] = INT_MAX;
memset(used, false, sizeof(used));
dis[st] = 0;
priority_queue<node>q;
q.push(node(st, 0));
while(!q.empty())
{
node tmp = q.top();
q.pop();
ll u = tmp.pos;
if(used[u])
continue;
used[u] = true;
for(int i=head[u]; i; i=edge[i].next)
{
ll v = edge[i].to;
if(dis[u] + edge[i].weight < dis[v])
{
dis[v] = dis[u] + edge[i].weight;
if(!used[v])
{
q.push(node(v, dis[v]));
}
}
}
}
}
// void print()
// {
// std::cout << "shortest path : ";
// for(int i=0; i<=n; i++)
// {
// std::cout << dis[i] << ' ';
// }
// std::cout << endl;
// }
void solve()
{
std::cin >> n >> m >> q;
for(int i=1; i<=m; i++)
{
ll u, v, w;
std::cin >> u >> v >> w;
addedge(u-1, v, w);
addedge(v, u-1, -w);
}
for(int i=1; i<=q; i++)
{
ll u, v;
std::cin >> u >> v;
dijkstra(u-1);
print();
// std::cout << "ans = ";
if(dis[v] == INT_MAX)
std::cout << "UNKNOWN\n";
else
std::cout << dis[v] << endl;
}
}
void run_code()
{
solve();
}
void run_code_with_time()
{
clock_t start, finish;
double totaltime;
start = clock();
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif// ONLINE_JUDGE
//================================================================
run_code();
//================================================================
#ifndef ONLINE_JUDGE
finish = clock();
totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
printf("\n此程式的運作時間為%.36lf秒!\n", totaltime);
#endif //ONLINE_JUDGE
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
run_code_with_time();
return 0;
}