HPU20級算協積分賽01
目錄
- HPU20級算協積分賽01
- A - Doin' Time
- B - Function
- C - Hack DSU!
- D - JOJO's Factory
- E - Keep Eating
- F - Select Half
- G - Strawberry Cakes
- H - Water Heater
- I - Knight
- J - Biscuit Generator
- K - Resale
宏定義用的比較多,主要是這倆
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
int型別讀入基本都使用的是快讀,換成scanf理論上不會有任何問題;
A - Doin’ Time
題目思路:
演算法:區間DP,快速冪求逆元,
狀態轉移方程:
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
]
[
j
]
,
f
[
i
]
[
k
]
+
f
[
k
+
1
]
[
j
]
+
(
x
?
y
)
2
)
f[i][j] = max(f[i][j] , f[i][k] + f[k + 1][j] + (x - y) ^ 2)
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+(x?y)2)
AC代碼:
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
using namespace std;
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0');ch = getchar(); }return x * w;}
typedef long long LL;
typedef pair<int , int > PII;
const int N = 310;
const int mod = 1000003;
const int inf = 0x3f3f3f3f;
LL f[N][N] , a[N];
int n , cost[N] , incost[N];
int qmi(int a , int k)
{
int res = 1;
while(k)
{
if(k & 1) res = (LL)res * a % mod;
a = (LL)a * a % mod;
k >>= 1;
}
return res;
}
int main()
{
n = read(); cost[0] = 1 , incost[0] = 1;
rep(i , 1 , n)
{
scanf("%lld" , &a[i]);
cost[i] = cost[i - 1] * a[i] % mod;
incost[i] = qmi(cost[i] , mod - 2);
}
rep(len , 2 , n)
{
for(int i = 1;i + len - 1 <= n;i ++)
{
int j = i + len - 1;
for(int k = i;k < j;k ++)
{
LL x = (LL)cost[k] * incost[i - 1] % mod;
LL y = (LL)cost[j] * incost[k] % mod;
f[i][j] = max(f[i][j] , f[i][k] + f[k + 1][j] + (x - y) * (x - y));
}
}
}
printf("%lld" , f[1][n]);
return 0;
}
B - Function
題目思路:
演算法:歐拉篩
思路:
眾所周知:歐拉篩相對于埃氏篩法的優化在于每個數只會被最小質因數篩掉,也正是這一步,把時間復雜度提升到了
o
(
n
)
o(n)
o(n),對歐篩稍作修改,此題就可以AC了,
- f[1 and 單個素數] = 1,這個很容易曬出來,只需要在
if(!st[i]) prmes[cnt ++] = i后面加一句f[i] = 1; - 如果要篩掉
primes[j] * i這個數,那么又分為兩種情況,
注意:這個時候,primes[j]一定是<= prmes[j] ? * ? i的最小質因子
1.i含有primes[j],那么屬于第二類, priems[j]是其最小質因子,算出i*primes[j]中prmes[j]的次數,根據奇偶,就可以從f[i]推出f[primes[j] * i]的值,如果是次數是奇數次,再乘一下,就會多一個primes[j]的值,如果是偶數,則f[primes[j] * i]=f[i]
2.如果不含有primes[j],那么primes[j]一定是i * primes[j]的最小質因子,且次數一定等于1,那么f[primes[j] * i]=i(第三種),
AC代碼:
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
using namespace std;
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0');ch = getchar(); }return x * w;}
typedef long long LL;
typedef pair<int , int > PII;
const int N = 1e7 + 10;
int primes[N] , cnt , n;
LL f[N] , sum[N];
bool st[N];
LL init(int n)
{
LL ans = 0;
f[1] = 1;
for(int i = 2;i <= n;i ++)
{
if(!st[i])
{
primes[cnt ++ ] = i;
f[i] = 1;
//第一種
}
for(int j = 0;primes[j] <= n / i;j ++)
{
st[primes[j] * i] = true;
//第二種
if(i % primes[j] == 0)
{
int count = 0;
int ri = i;
while(ri % primes[j] == 0)
{
count ++;
ri /= primes[j];
}
if(count & 1) f[primes[j] * i] = f[i] * primes[j];
else f[primes[j] * i] = f[i];
break;
}
//第三種
f[primes[j] * i] = i;
}
}
rep(i , 1 , n) ans += f[i];
return ans;
}
int main()
{
n = read();
printf("%lld" , init(n));
return 0;
}
C - Hack DSU!
題目思路:
AC代碼:
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
using namespace std;
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0');ch = getchar(); }return x * w;}
typedef long long LL;
typedef pair<int , int > PII;
int n , T;
int main()
{
n = read() , T = read();
printf("%d %d\n" , n , 1);
pre(i , n - 1 , 2) printf("%d %d\n" , i , i - 1);
printf("%d %d\n" , 1 , n);
return 0;
}
D - JOJO’s Factory
題目思路:
AC代碼:
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
using namespace std;
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0');ch = getchar(); }return x * w;}
typedef long long LL;
typedef pair<int , int > PII;
int n , m , counter_1 , counter_2;
unordered_map<int , int> bj1 , bj2;
int main()
{
n = read() , m = read();
rep(i , 1 , m)
{
int a , b;
a = read() , b = read();
bj1[a] ++; bj2[b] ++;
if(bj1[a] == n) counter_1 ++;
if(bj2[b] == n) counter_2 ++;
}
printf("%d" , min(n - counter_1 , n - counter_2));
return 0;
}
E - Keep Eating
題目思路:
AC代碼:
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
using namespace std;
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0');ch = getchar(); }return x * w;}
typedef long long LL;
typedef pair<int , int > PII;
LL sum;
int n , k , x;
int main()
{
n = read() , k = read();
rep(i , 1 , n)
{
x = read();
sum += x;
}
printf("%lld" , sum < k ? 0 : sum - k + (k / 2));
return 0;
}
F - Select Half
題目思路:
AC代碼:
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
using namespace std;
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0');ch = getchar(); }return x * w;}
typedef long long LL;
typedef pair<int , int > PII;
const int N = 2e5 + 10;
int a[N] , n;
LL f[N] , sum[N];
int main()
{
n = read();
rep(i , 1 , n)
{
a[i] = read();
if(i & 1) sum[i] = sum[i - 2] + a[i];
}
rep(i , 2 , n)
{
if(i & 1) f[i] = max(f[i - 2] + a[i] , f[i - 1]);
else f[i] = max(f[i - 2] + a[i] , sum[i - 1]);
}
printf("%lld" , f[n]);
return 0;
}
G - Strawberry Cakes
題目思路:
模擬
代碼分為三步:
1.給每個帶有草莓的標號
2.按照行拓展
3.按照列拓展
下面以樣例為例子:
第一步后,答案陣列更新為:

第二步后,答案陣列更新為:

可以看到,答案已經更新完了,而且一定滿足題目要求,
那么第三步呢?
可以想象,按照行向左右拓展,如果存在一行沒有一個草莓,那么這一行都是0,所以按照列上下拓展是必須的,
這也是第三步的意義,
AC代碼:
Select Code
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
using namespace std;
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0');ch = getchar(); }return x * w;}
typedef long long LL;
typedef pair<int , int > PII;
const int N = 310;
int n , m , k;
char g[N][N];
int ans[N][N];
int main()
{
n = read() , m = read() , k = read();
rep(i , 1 , n) scanf("%s" , g[i] + 1);
//第一步
rep(i , 1 , n) rep(j , 1 , m)
if(g[i][j] == '#') ans[i][j] = k --;
//第二步
rep(i , 1, n)
{
rep(j , 2 , m)
if(ans[i][j] == 0) ans[i][j] = ans[i][j - 1];
pre(j , m - 1 , 1)
if(ans[i][j] == 0) ans[i][j] = ans[i][j + 1];
}
//第三步
rep(i , 1 , m)
{
rep(j , 2 , n)
if(ans[j][i] == 0) ans[j][i] = ans[j - 1][i];
pre(j , n - 1 , 1)
if(ans[j][i] == 0) ans[j][i] = ans[j + 1][i];
}
//輸出答案
rep(i , 1 , n)
rep(j , 1 , m)
printf("%d%c", ans[i][j] , j == m ? '\n' : ' ');
return 0;
}
H - Water Heater
題目思路:
AC代碼:
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
using namespace std;
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0');ch = getchar(); }return x * w;}
typedef long long LL;
typedef pair<int , int > PII;
const int N = 2e5 + 10;
int n , s , t , p , w;
LL a[N];
int main()
{
n = read() , w = read();
int st = 0x3f3f3f3f , la = -1;
rep(i , 1 , n)
{
s = read() , t = read() , p = read();
s ++ , t ++;
st = min(s , st);
la = max(t , la);
a[s + 1] += p;
a[t + 1] -= p;
}
bool fal = true;
// cout << st << " " << la << endl;
rep(i , st , la)
{
a[i] = a[i - 1] + a[i];
// printf("%d %d\n" , i , a[i]);
if(a[i] > w)
{
// cout << i << endl;
fal = false;
break;
}
}
if(fal) puts("Yes");
else puts("No");
return 0;
}
I - Knight
題目思路:
AC代碼:
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
using namespace std;
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0');ch = getchar(); }return x * w;}
typedef long long LL;
typedef pair<int , int > PII;
const int mod = 1e9 + 7;
const int N = 1e7 + 10;
LL f[N];
LL x , y;
LL qmi(LL a , LL k)
{
LL res = 1;
while(k)
{
if(k & 1) res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}
void init()
{
f[0] = 1;
f[1] = 1;
rep(i , 2 , 1e7) f[i] = f[i - 1] * i % mod;
}
int main()
{
init();
// cout << f[5] << endl;
LL ans = 0;
x = read() , y = read();
LL a1 = y * 2 - x;
LL b1 = 2 * x - y;
// cout << a1 << " " << b1 << endl;
if(a1 % 3 != 0 || b1 % 3 != 0 || a1 < 0 || b1 < 0)
{
// cout << 1 << endl;
printf("0");
}
else
{
a1 = a1 / 3;
b1 = b1 / 3;
LL s = a1 + b1;
// cout << f[1] << endl;
printf("%lld" , (f[s] * qmi(f[a1] , mod - 2) % mod) * qmi(f[b1] , mod - 2) % mod);
}
return 0;
}
J - Biscuit Generator
題目思路:
AC代碼:
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
using namespace std;
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0');ch = getchar(); }return x * w;}
typedef long long LL;
typedef pair<int , int > PII;
LL ans = 0;
int a , b;
double t;
int main()
{
a = read() , b = read();
scanf("%lf" , &t);
for(int i = 1;i * a <= t + 0.5;i ++)
{
ans += b;
}
printf("%lld" , ans);
return 0;
}
K - Resale
題目思路:
AC代碼:
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
using namespace std;
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0');ch = getchar(); }return x * w;}
typedef long long LL;
typedef pair<int , int > PII;
const int N = 500;
int n , v[N] , w[N];
LL ans;
int main()
{
n = read();
rep(i , 1 , n) v[i] = read();
rep(i , 1 , n) w[i] = read();
rep(i , 1 , n) if(v[i] > w[i]) ans += v[i] - w[i];
printf("%lld" , ans);
return 0;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/287698.html
標籤:其他
上一篇:物體朝向目標(u3d)
下一篇:Xlua開發筆記:網路圖片加載
