HDU-2018中国大学生程序设计竞赛-网络选拔赛-部分代码
这次抽周末打网络赛，两个半小时就溜了，只过了五道题，后边因为网吧电脑和键盘以及 HDU H D U 的原因，被打自闭了，太难了。
由于不是我自己的电脑，所以整理题解有些麻烦了，现在先给出五道题的代码，如果有时间了，题解慢慢补吧……大概率是没有了吧！
1001 Buy and Resell
描述
代码
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e5 + 10;
int n;
int a[MAXN];
struct cmp_pq2
{
bool operator () (const pair<int, int> &x, const pair<int, int> &y) const
{
return a[x.second] > a[y.second];
}
};
struct cmp_pq1
{
bool operator () (const int &x, const int &y)
{
return a[x] > a[y];
}
};
int main()
{
int T;
cin >> T;
while (T--)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
priority_queue<int, vector<int>, cmp_pq1> pq1;
priority_queue<pair<int, int>, vector<pair<int, int> >, cmp_pq2> pq2;
for (int i = 1; i <= n; i++)
{
int p = 0, s = 0;
if (!pq1.empty() && a[pq1.top()] < a[i])
{
p = a[i] - a[pq1.top()];
}
if (!pq2.empty() && a[pq2.top().second] < a[i])
{
s = a[i] - a[pq2.top().second];
}
if (!p && !s)
{
pq1.push(i);
}
else if (s >= p)
{
int fis =pq2.top().first, sec = pq2.top().second;
pq2.pop();
pq2.push({fis, i});
pq1.push(sec);
}
else
{
pq2.push({pq1.top(), i});
pq1.pop();
}
}
ll res = 0, cnt = pq2.size() * 2;
while (!pq2.empty())
{
res += a[pq2.top().second] - a[pq2.top().first];
pq2.pop();
}
printf("%lld %lld\n", res, cnt);
}
return 0;
}1003 Dream
描述
代码
#include <cstdio>
#include <iostream>
using namespace std;
int p;
int main()
{
int T;
cin >> T;
while (T--)
{
scanf("%d", &p);
for (int i = 0; i < p; i++)
{
for (int j = 0; j < p; j++)
{
printf("%d%c", (i + j) % p, j == p - 1 ? '\n' : ' ');
}
}
for (int i = 0; i < p; i++)
{
for (int j = 0; j < p; j++)
{
printf("%d%c", (i * j) % p, j == p - 1 ? '\n' : ' ');
}
}
}
return 0;
}1004 Find Integer
描述
代码
#include <iostream>
#include <cstdio>
using namespace std;
long long n, a, b, c;
int main()
{
int T;
cin >> T;
while (T--)
{
scanf("%d%d", &n, &a);
if (n > 2)
{
printf("-1 -1\n");
}
else if (n == 1)
{
printf("%d %d\n", 1, a + 1);
}
else if (n == 0)
{
printf("-1 -1\n");
}
else
{
if (a > 1)
{
if (a & 1)
{
long long n = a >> 1;
printf("%lld %lld\n", 2 * n * n + 2 * n, 2 * n * n + 2 * n + 1);
}
}
if (a > 4)
{
if ((a & 1) == 0)
{
long long n = a >> 1;
printf("%lld %lld\n", n * n - 1, n * n + 1);
}
}
if (a == 1 || a == 2)
{
printf("-1 -1\n");
}
if (a == 4)
{
printf("3 5\n");
}
}
}
return 0;
}1005 GuGu Convolution
描述
代码
#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 1e6+ 5;
ll r,p;
struct juz {
ll x, y;
juz() { x = 0; y = 0; }
juz operator*(const juz &b) const{
juz ans;
ans.x = (x*b.x%p + y * b.y%p*r) % p;
ans.y = (x*b.y%p + y * b.x) % p;
return ans;
}
juz operator-(const juz &b) const {
juz ans;
ans.x = x - b.x;
ans.y = y - b.y;
return ans;
}
}z1,z2,cot;
juz qpow(juz x, ll y) {
juz z ;
z.x = 1;
z.y = 1;
while (y) {
if (y & 1)z =z*x;
x=x*x;
y /= 2;
}
return z;
}
int f[1000005];
void init() {
ll i, j;
for (i = 1; i*i <= maxn; i++)f[i*i] = i;
for (i = 1; i <= maxn; i++)
for (j = i + i; j <= maxn; j += i)f[j] = max(f[j], f[i]);
}
int main() {
#ifdef LOCAL
freopen("D:/input.txt", "r", stdin);
#endif
ll i, j, a, b, n;
init();
int t;
cin>>t;
while(t--)
{
scanf("%lld%lld%lld%lld", &a, &b, &n, &p);
p *= 2;
r = b;
z1.x = a,z1.y = 1;
z2.x = a, z2.y = p - 1;
cot = qpow(z1, n) - qpow(z2, n);
cot.y = (cot.y*f[b] % p + p) % p / 2;
printf("1 %lld %lld\n", cot.y, b / (f[b] * f[b]));
}
return 0;
}1009 Tree and Permutation
描述
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
struct TNode
{
int v, w;
TNode() {}
TNode(int v, int w) : v(v), w(w) {}
};
int N;
long long ans;
long long sum[MAXN];
long long inv[MAXN];
vector<TNode> G[MAXN];
void dfs(int root, int pre)
{
sum[root] = 1;
for (int i = 0; i < G[root].size(); i++)
{
TNode &e = G[root][i];
int s = e.v;
if (s == pre)
{
continue;
}
dfs(s, root);
sum[root] += sum[s];
sum[root] %= MOD;
ans += (long long)(sum[s] * (N - sum[s]) * e.w);
ans %= MOD;
}
}
void init()
{
inv[0] = 1;
for (int i = 1; i < MAXN; i++)
{
inv[i] = inv[i - 1] * i % MOD;
}
}
int main()
{
init();
while (cin >> N)
{
ans = 0;
memset(sum, 0, sizeof(sum));
for (int i = 0; i <= N; i++)
{
G[i].clear();
}
int X, Y, L;
for (int i = 1; i < N; i++)
{
scanf("%d%d%d", &X, &Y, &L);
G[X].push_back(TNode(Y, L));
G[Y].push_back(TNode(X, L));
}
dfs(1, 0);
printf("%lld\n", ans * inv[N - 1] % MOD * 2 % MOD);
}
return 0;
}1010 YJJ’s Salesman
描述
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
int mx[4 * maxn];
int b[maxn];
struct Node
{
int x;
int y;
int val;
bool operator <(const Node &p)const
{
if(x == p.x)return y < p.y;
return x < p.x;
}
}a[maxn];
int ql, qr;
int query(int o, int l, int r)
{
if(qr < ql)return 0;
if(ql <= l && qr >= r)
{
return mx[o];
}
int m = l + (r - l) / 2;
int ans = - 1;
if(ql <= m)ans = max(ans, query(o * 2, l, m));
if(qr > m)ans = max(ans, query(o * 2 + 1, m + 1, r));
return ans;
}
void update(int o, int l, int r, int pos, int val)
{
if(l == r)
{
mx[o] = max(val, mx[o]) ;
//cout << l << " " << mx[o] << endl;
return ;
}
int m = l + (r - l) / 2;
if(pos <= m)update(o * 2, l, m, pos, val);
else update(o * 2 + 1, m + 1, r, pos, val);
mx[o] = max(mx[o * 2], mx[o * 2 + 1]);
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int n;
scanf("%d", &n);
int cnt = 0;
for(int i = 0; i < n; i++)
{
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].val);
b[cnt++] = a[i].y;
}
memset(mx, 0, sizeof(mx));
sort(b, b + cnt);
int m = 1;
for(int i = 1; i < cnt; i++)
{
if(b[i] != b[i - 1])b[m++] = b[i];
}
sort(a, a + n);
int res = -1;
for(int i = 0; i < n; i++)
{
vector<pair<int, int> >cc;
int mxx = -1;
int j;
for(j = i; j < n; j++)
{
if(a[j].x != a[i].x)break;
int pos1 = lower_bound(b, b + m, a[j].y) - b;
int pos2 = lower_bound(b, b + m, a[j].y - 1) - b;
if(b[pos2] != a[j].y - 1)pos2 --;
ql = 0;qr = pos2;
int ans = query(1, 0, m - 1);
ql = pos1;
qr = pos1;
ans = max(ans + a[j].val, query(1, 0, m - 1));
if(ans > mxx)
{
mxx = ans;
}
else
{
ans = mxx;
}
res = max(res, ans);
cc.push_back(make_pair(pos1, ans));
}
for(int k = 0; k < cc.size(); k++)
{
update(1, 0, m - 1, cc[k].first, cc[k].second);
}
i = j - 1;
}
cout << res << endl;
}
return 0;
}啊啊啊啊，才发现竟然是六道题，昨天下午两点半我撤了以后，我队友明明去参加面试了，怎么面试完回来又 A A <script type="math/tex" id="MathJax-Element-2">A</script> 了一题，好强啊……从代码风格上可以区分出来哪些题是我写的，哪些不是，就这样把，懒得都格式化成我的习惯了。
有趣的是，网赛都打得好猛啊！！！感觉人均五题啊……不对，是队。尤其是我们河南，每次网络赛成绩都出奇的好，太牛逼了吧！！！
拼多多集团-PDD公司福利 474人发布
