1001 Road To The 3rd Building
链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1001&cid=884
题意：
n 个点根为 1 的树，每个点上有价值ai的苹果
树上有 m 个监控：x k c
在点 x 有一个监控，可以检测到最短距离在 k 以内的所有子树上的点
破坏该监控需要 c,求最大收获
思路:
计算每个数对答案的贡献。对于S_1，贡献为(1 * S_1 / 1) + (1 * S1 /2) + (1 * S1/3) + ......+(1 * S1 / n)；对于S2，贡献为(1 * S2 / 1) + (2 * S2 /2) + (2 * S2/3) + ......+(2 * S2 / (n - 1)) + (1 * S2 / n)......将这些贡献的计算总结在表格中。先暂时不看乘号前的数字，乘号后的数规律为：Si / k(k [1,N])。然后单独看乘号前的数，会发现这个NN的表格，最外圈全为1，第二圈全为2，第三圈全为3，直到第N/2圈。因此计算答案时一圈一圈的算。在计算第 i 圈时，我的计算方法是先计算这一圈的第一列和最后一列的和，然后计算第一行和最后一行去掉首尾的和。
*代码：**
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
//#define ll long long
const ll N = 1e3 + 5;
const ll maxn = 2e5 + 20;
const ll mod = 1000000007;
ll inv[maxn], vis[maxn], dis[maxn];
ll max(ll a, ll b) { return a > b ? a : b; }
ll min(ll a, ll b) { return a < b ? a : b; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
map<ll, ll> mp;
ll ksm(ll a, ll b)
{
a %= mod;
ll ans = 1ll;
while (b)
{
if (b & 1)
ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1ll;
}
return ans;
}
ll dp[105][16005];
string p = "abacaba";
queue<ll> qk, q;
vector<ll> vec;
ll sumx[maxn], sumy[maxn], sumk[maxn];
int main()
{
ll t, n, ans;
scanf("%lld", &t);
while (t--)
{
memset(sum, 0, sizeof sum);
memset(sumx, 0, sizeof sumx);
memset(sumy, 0, sizeof sumy);
memset(sumk, 0, sizeof sumk);
scanf("%lld", &n);
ans = 0;
for (ll i = 1ll; i <= n; i++)
scanf("%lld", &a[i]), sum[i] = (sum[i - 1ll] + a[i]) % mod;
for (ll i = 1ll; i <= n; i++)
sumx[i] = (sumx[i - 1ll] + sum[i]) % mod;
ll k = n;
for (ll i = 1ll; i <= n; i++)
sumy[i] = (sumy[i - 1ll] + a[k]) % mod, k--;
for (ll i = 1ll; i <= n; i++)
sumk[i] = (sumk[i - 1ll] + sumy[i]) % mod;
for (ll i = 1ll; i <= n; i++)
{
ans = (ans + ((((i * sum[n] % mod) - sumx[i - 1ll] - sumk[i - 1ll] + mod) % mod) * ksm(i, mod - 2ll) % mod)) % mod;
}
ll np = (((n + 1ll) * n) / 2ll) % mod;
printf("%lld\n", ((ans % mod) * (ksm(np, mod - 2ll) % mod) % mod));
}
}1002 Little Rabbit's Equation
链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&cid=884
题意：
给定一个运算表达式，形式上满足 num1 op num2=num3(op∈{+,−,∗,/})
问你这个表达式在何种进制下（2−16）成立，输出最小的可行进制。
思路：很水的一个暴力题。只要将输入的表达式拆分成三个字符串，然后枚举所有进制，当小字符串在当前进制下合法（所有数位上的数小于进制），将其转化为十进制数，判断十进制下表达式是否成立。如果都不成立就输出-1。
代码：
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define LL long long
#define PII pair<int, int>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
inline int read(){
char c = getchar();
while(!isdigit(c)) c = getchar();
int x = 0;
while(isdigit(c)){
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
inline bool op(char x){
if(x == '+') return 0;
if(x == '-') return 0;
if(x == '*') return 0;
if(x == '/') return 0;
if(x == '=') return 0;
return 1;
}
char s[20];
inline void cal(int &cur, string &x){
int len = strlen(s);
while(cur < len && op(s[cur])){
if(x.size() == 0) if(s[cur] == '0'){
cur++;
continue;
}
x += s[cur++];
}
cur++;
}
inline LL change(int cur, string x){
int len = x.size();
LL Base = 1;
LL ans = 0;
for(int i = len - 1; i >= 0; --i){
int c;
if(x[i] >= '0' && x[i] <= '9') c = x[i] - '0';
else if(x[i] <= 'F' && x[i] >= 'A') c = x[i] - 'A' + 10;
if(c >= cur) return -1;
ans += c * Base;
Base = Base * cur;
}
return ans;
}
inline bool judge(LL a, LL b, LL c, char op){
if(op == '+') if(a + b == c) return 1;
if(op == '-') if(a - b == c) return 1;
if(op == '*') if(a * b == c) return 1;
if(op == '/') if(c * b == a) return 1;
return 0;
}
int main(){
while(~scanf(" %s", s)){
string x, y, z;
int cur = 0;
char op;
cal(cur, x); op = s[cur - 1];
cal(cur, y);
cal(cur, z);
int ans = -1;
for(int i = 2; i <= 16; ++i){
LL a, b, c;
a = change(i, x); if(a == -1) continue;
b = change(i, y); if(b == -1) continue;
c = change(i, z); if(c == -1) continue;
if(judge(a, b, c, op)){
ans = i;
break;
}
}
printf("%d\n", ans);
}
return 0;
}1006 A Very Easy Graph Problem
链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1006&cid=884
思路：
因为边权是按照输入顺序递增的。且对于第 i 条边，前 i - 1 条边的权值和都小于第 i 条边，因此按照输入顺序建新图，当输入边的两个端点不属于同一连通块时在新图中加入这条边，输入结束后的新图必定是一颗树，且两点间的距离必定在旧图中也是最小的。随意选取树上的一个点作为根节点，跑一遍DFS，记录下每个点以及它所有子树的权值为1的点的个数和以及权值0的点的个数和。因为题目的限制，因此对答案有贡献的边必定都在树上。又根据乘号后的表达式的要求，某一条边被遍历的次数必定是这条边下面的所有权值1的点的个数 * 这条边上面所有权值0的点的个数 + 下面所有权值0的点的个数 * 上面所有权值1的点的个数。因此只要直到一个点的所有子结点中有多少个权值flag结点，将总flag权值结点个数-子结点中flag权值结点个数就是上面的flag权值结点个数。具体的看代码吧。
代码：
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define LL long long
#define pii pair<int, int>
const LL mod = 1e9 + 7;
const int maxn = 2e5 + 5;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
const double pi = acos(-1.0);
vector<int> G[maxn];
LL w[maxn];
int a[maxn], u[maxn], v[maxn];
int pre[maxn], dfn[maxn];
bool add[maxn];
int find(int x) { return x == pre[x] ? x : pre[x] = find(pre[x]); }
int cnt, sum[2], num[maxn][2];
void dfs(int now, int fa) {
dfn[now] = ++cnt;
int len = G[now].size();
num[now][0] = (a[now] == 0);
num[now][1] = (a[now] == 1);
for(int i = 0; i < len; ++i) {
int son = G[now][i];
if(son == fa) continue;
dfs(son, now);
num[now][0] += num[son][0];
num[now][1] += num[son][1];
}
}
int main() {
w[0] = 1LL;
for(int i = 1; i < maxn; ++i) {
w[i] = w[i - 1] * 2LL % mod;
}
int T; cin >> T;
while(T--) {
int n, m;
scanf("%d%d", &n, &m);
sum[0] = sum[1] = 0;
for(int i = 1; i <= n; ++i) {
scanf("%d", a + i);
sum[0] += (a[i] == 0);
sum[1] += (a[i] == 1);
pre[i] = i; G[i].clear();
}
memset(add, false, sizeof add);
for(int i = 1; i <= m; ++i) {
scanf("%d%d", u + i, v + i);
int fu = find(u[i]);
int fv = find(v[i]);
if(fu == fv) continue;
pre[fv] = fu;
add[i] = true;
G[u[i]].push_back(v[i]);
G[v[i]].push_back(u[i]);
}
cnt = 0; dfs(1, 0);
LL ans = 0;
for(int i = 1; i <= m; ++i) {
if(!add[i]) continue;
int fa = u[i], son = v[i];
if(dfn[fa] > dfn[son]) swap(fa, son);
int fa0 = sum[0] - num[son][0];
int fa1 = sum[1] - num[son][1];
ans = (ans + w[i] * (fa0 * num[son][1] % mod) % mod) % mod;
ans = (ans + w[i] * (fa1 * num[son][0] % mod) % mod) % mod;
}
printf("%lld\n", ans);
}
return 0;
}
1009 Divisibility
链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1009&cid=884
题意：
水题，没做上，丢人
代码：
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
int main()
{
ll t, n, ans;
scanf("%lld", &t);
while (t--)
{
ll n, x;
cin >> n >> x;
if ((n % x) == 1)
cout
<< "T" << endl;
else
{
cout << "F" << endl;
}
}
}
京公网安备 11010502036488号