2018 CCPC网络赛
前言
月底3个DDL，终于赶完了一个！
边赶边补题，QAQ
Find Integer - HDU - 6441
链接
https://cn.vjudge.net/problem/HDU-6441
题意
给定n与a，找出b,c使得满足 a^n + b^n = c^n，不存在输出-1 -1
思路 —— 费马大定理 + 勾股数规律
签到题，今年做的时候拿去构造了，补题发现原来有勾股数规律
- n >= 3 时，根据费马大定理，直接无解
- n == 0 时，等式不成立，无解
- n == 1 时，直接输出
b = 1, c = a + 1 - n == 2 时，直接贴以下勾股数规律（以后也方便查，[滑稽.jpg]
① 2n + 1, 2n^2 + 2n, 2n^2 + 2n + 1 为勾股数
② 2(n + 1), n^2 + 2n, n^2 + 2n + 2 为勾股数
③ m^2 - n^2, 2mn, m^2 + n^2 为勾股数
对于b,c非正的也直接-1 -1
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
int main(){
int t;
scanf("%d", &t);
while(t--){
int n, a;
scanf("%d%d", &n, &a);
if(n >= 3 || n == 0){
puts("-1 -1");
}else if(n == 1){
printf("%d %d\n", 1, a + 1);
}else if(a <= 2){
puts("-1 -1");
}else{
if(a & 1){
int tmp = a / 2;
printf("%d %d\n", 2*tmp*tmp + 2*tmp, 2*tmp*tmp + 2*tmp + 1);
}else{
int tmp = a / 2 - 1;
printf("%d %d\n", tmp*tmp + 2*tmp, tmp*tmp + 2*tmp + 2);
}
}
}
}
YJJ’s Salesman - HDU 6447
链接
https://cn.vjudge.net/problem/HDU-6447
题意
在一幅地图上，从(0, 0)往(10^9, 10^9)走，每次只能从(x, y)走到(x+1, y)或者(x, y+1)或者(x+1,y+1)。在地图上有一些村庄，给出村庄的坐标(x, y)和价值v，当且仅当你从(x−1,y−1) 走到村庄时，你才可以获得价值v，求最大能获得的总价值是多少？
思路 —— 离散化 + 树状数组优化DP
这道题说多了都是泪，比赛怎么都没想到，比赛完马上就有思路了QAQQQQ
首先对y轴进行离散化以建立树状数组，然后对输入的点排序，以x轴先正序排，再y轴逆序排，此时可列出DP方程 dp[y] = max{dp[1], dp[2], ..., dp[y - 1] + v，过程取最大值就是答案
对y轴逆序排序是显而易见的，因为上述DP方程需要保证他们的x点位于此时的x点的左侧，若正序排则dp[y'](y' < y)已被更新，会影响结果，逆序则不会有影响
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 1e5 + 15;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
} while('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
} return x * f;
}
struct Node{
int x, y, val;
bool operator < (const Node& b) const{
if(x != b.x) return x < b.x;
else return y > b.y;
}
};
int maxy[N << 2];
int mpy[N], py;
Node a[N];
int tree[N];
inline void init() {
memset(tree, 0, sizeof(tree));
py = 0;
}
inline int lowbit(int idx){ return (idx & -idx); }
int getSum(int idx){
int sum;
for(sum = 0; idx > 0; idx -= lowbit(idx)){
sum = max(sum, tree[idx]);
}
return sum;
}
void update(int idx, int val){
while(idx < N){
tree[idx] = max(tree[idx], val);
idx += (idx & -idx);
}
}
inline int getIdx(int val){
return lower_bound(mpy + 1, mpy + py + 1, val) - mpy;
}
int main(){
int t = read();
while(t--){
init();
int m = read();
for(int i = 1; i <= m; i++){
a[i].x = read(), a[i].y = read(), a[i].val = read();
mpy[i] = a[i].y;
}
sort(mpy + 1, mpy + m + 1);
py = unique(mpy + 1, mpy + m + 1) - mpy - 1;
sort(a + 1, a + m + 1);
int ans = 0;
for(int i = 1; i <= m; i++){
int pos = getIdx(a[i].y );
int val;
if(pos != 1) val = getSum(pos - 1) + a[i].val;
else val = a[i].val;
ans = max(ans, val);
update(pos, val);
}
printf("%d\n", ans);
}
}
Tree and Permutation - HDU - 6446
链接
https://cn.vjudge.net/problem/HDU-6446
题意
对树的顶点做全排列，对每一个排列都按该排列遍历顶点，问所有经过的边的权值总和（按重数计）
思路 —— 拆分思想 + 树形DP
假设存在N个点，现在单独对某一条边考虑，考虑在全排列中相邻的情况，即在(N-2)个数的全排列中插入，那么其相邻的排列总数应为(N-2)! * (N-1) * 2 = (n-1)! * 2，故对任意一条边都会经过(n-1)! * 2次，故可用树形DP先算出树上点点距离之和，再乘上经过次数，即可得到答案
关于树形DP方面，可以将树上点点距离和归为树上相邻边权值乘上经过次数，一条相邻的边经过的总次数 = 其位于下方的点的子树点总数 * 其余的点总数，那么可列出DP方程dp[u] = (dp[u] + dp[v] + cnt[v] * (n - cnt[v]) * w
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 15;
const int MOD = 1e9 + 7;
typedef long long ll;
struct edge{
int v, w, nxt;
};
edge e[N << 1];
int head[N], tot;
ll dp[N];
int cnt[N];
ll mulfac[N];
inline void init(){
memset(head, -1, sizeof(head));
tot = 0;
mulfac[0] = 1;
for(int i = 1; i < N; i++){
mulfac[i] = (mulfac[i - 1] * i) % MOD;
}
}
inline void addEdge(int u, int v, int w){
e[tot] = edge{v, w, head[u]};
head[u] = tot++;
}
void dfs(int u, int pre, int n){
cnt[u] = 1, dp[u] = 0;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(v == pre) continue;
dfs(v, u, n);
cnt[u] += cnt[v];
dp[u] = (dp[u] + dp[v] + ((ll)cnt[v] * (n - cnt[v]))%MOD * e[i].w % MOD) % MOD;
}
}
int main(){
int n;
while(~scanf("%d", &n)){
init();
for(int i = 1; i <= n - 1; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
dfs(1, -1, n);
ll ans = ((mulfac[n - 1] * 2)%MOD * dp[1]) % MOD;
printf("%lld\n", ans);
}
return 0;
}
Dream - HDU - 6440
链接
https://cn.vjudge.net/problem/HDU-6440
题意
重定义加法和乘法，使得(m+n)^p = m^p + n^p，其中p为质数，m,n < p，且需满足给定集合的封闭性
思路 —— 费马小定理
本题完全是蒙对的QAQ，队友说要不构造一下样例，输出(i+j)%p和(i*j)%p算了，然后就眼睁睁看它AC了hhhhh
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
const int N = 15 + 15;
typedef long long ll;
const ll inf = 5e18 + 15;
int main(){
int t;
scanf("%d", &t);
while(t--){
int p;
scanf("%d", &p);
for(int i = 0; i < p; i++){
for(int j = 0; j < p; j++){
printf("%d", (i + j) % p);
if(j < p - 1) putchar(' ');
}
puts("");
}
for(int i = 0; i < p; i++){
for(int j = 0; j < p; j++){
printf("%d", (i * j) % p);
if(j < p - 1) putchar(' ');
}
puts("");
}
}
}
Buy and Resell - HDU - 6438
链接
https://cn.vjudge.net/problem/HDU-6438
题意
给定n天，每天有个价格，可以买一个物品，也可以把手中的物品卖掉，问能取得的最大价值是多少，在取得这一最大价值的同时，要求买卖次数最小
思路 —— 思维 + 贪心
本题唯一的思维点没想到T^T，那就是对于卖掉的物品，再买相当于不买不卖，于是不需要担心选错物品，只需要贪心即可
贪心的方法为，维护一个优先队列，将卖掉的物品和不买不卖的物品维护在其中，按顺序遍历数组维护这一优先队列，使得价值小的物品或价值同样小但已卖出的物品先出队（为了买卖次数最小），遍历到数组某一元素时，若队头比这一元素小，则进行买卖更新信息以及物品被卖或不买不卖的信息，同时删除优先队列中已买的物品，累加得到最后的答案
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
struct Node{
int idx;
ll val;
bool tag;
bool operator < (const Node& b) const{
if(val != b.val) return val > b.val;
else return tag < b.tag;
}
};
int main(){
int t;
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
priority_queue<Node> que;
ll ans = 0;
int cnt = 0;
for(int i = 1; i <= n; i++){
ll tmp;
scanf("%lld", &tmp);
bool tag = 0;
if(!que.empty() && que.top().val < tmp){
ans += (tmp - que.top().val);
tag = 1;
cnt += 2;
Node u = que.top();
que.pop();
if(u.tag == 1){
cnt -= 2;
u.tag = 0;
que.push(u);
}
}
que.push(Node{i, tmp, tag});
}
printf("%lld %d\n", ans, cnt);
}
}
Neko’s loop - HDU - 6444
链接
https://cn.vjudge.net/problem/HDU-6444
题意
一个有n个数的环，每次循环走k步，走到每个点都有具体的权值，问在任意点出发最多走m步的情况下，一开始需要拥有多少价值才能使最终总价值不少于s。(from: http://www.cnblogs.com/fht-litost/p/9551047.html)
思路 —— 裴蜀定理 + 单调队列求不超过间距k的区间和最大值
由裴蜀定理知，(i+k)%n的循环节是n/gcd(n,k)大小为，故用unordered_set暴力维护下标，并用vector暴力记录循环节的元素
然后用对于每一循环节，
- 若sum <= 0 且 m / size > 0，则答案可以是最大区间和
- 若sum > 0 且 m / size > 0，则答案可以是
p * sum[sz] + maxn_seg或(p - 1) * sum[sz] + maxn_all，即把所有圈都跑完再跑剩余的 m % size，或者少跑一圈再跑最大区间和 - 答案还可以是间距不超过 m % size 的区间最大和
对于以上情况求个最大即可
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <deque>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 2e4 + 5;
ll sum[N], a[N];
vector<int> vec[N];
int pp;
ll getSegmentMaxn(int sz, int m){
ll ans = 0;
deque<int> que;
que.push_back(0);
for(int i = 1; i <= sz; i++){
while(!que.empty() && sum[que.back()] > sum[i]) que.pop_back();
while(!que.empty() && i - que.front() > m) que.pop_front();
que.push_back(i);
int j = que.front();
ans = max(ans, sum[i] - sum[j]);
}
return ans;
}
inline void getSum(const vector<int>& vec){
sum[0] = 0;
for(int i = 1; i <= vec.size(); i++){
sum[i] = sum[i - 1] + vec[i - 1];
}
}
inline void init(){
for(int i = 0; i < N; i++) vec[i].clear();
pp = 0;
}
int main(){
int t, csn = 1;
scanf("%d", &t);
while(t--){
init();
unordered_set<int> st;
int n, m, k;
ll s;
scanf("%d%lld%d%d", &n, &s, &m, &k);
for(int i = 0; i < n; i++){
scanf("%lld", &a[i]);
st.emplace(i);
}
for(int i = 0; i < n; i++){
int x = i;
if(st.count(x)){
while(st.count(x)){
vec[pp].push_back(a[x]);
st.erase(x);
x = (x + k) % n;
}
pp++;
}
}
ll ans = 0;
for(int i = 0; i < pp; i++){
int sz = vec[i].size();
int p = m / sz;
int r = m % sz;
for(int j = 0; j < sz; j++){
vec[i].push_back(vec[i][j]);
}
getSum(vec[i]);
ll maxn_all = getSegmentMaxn(sz << 1, sz);
ll maxn_seg = getSegmentMaxn(sz << 1, r);
ll cur_ans = 0;
if(p && sum[sz] > 0){
cur_ans = max(p * sum[sz] + maxn_seg, (p - 1) * sum[sz] + maxn_all);
}else if(p && sum[sz] <= 0){
cur_ans = max(cur_ans, maxn_all);
}
cur_ans = max(cur_ans, maxn_seg);
ans = max(cur_ans, ans);
}
printf("Case #%d: %lld\n", csn++, max(s - ans, 0LL));
}
}
