题目链接
被C题卡到了,没发觉规律,还是思维不行。
A题
题意:让你构造一个序列,恰好有A个正整数,B个负整数,并且所有数各不相同且总和为0
思路:按照要求简单构造即可。
int main()
{
IOS;
int a, b;
cin >> a >> b;
if(a > b)
{
int sum = 0;
for(int i = 1 ; i <= a ; i ++)
cout << i << " ", sum += i;
for(int i = 1 ; i < b ; i ++)
cout << -i << " ", sum -= i;
cout << -sum << endl;
}
else
{
int sum = 0;
for(int i = 1 ; i <= b ; i ++)
cout << -i << " ", sum += i;
for(int i = 1 ; i < a ; i ++)
cout << i << " ", sum -= i;
cout << sum << endl;
}
return 0;
}
B题
题意:给你一个n个数的整数序列,每次可以选择一个数,使得大于等于它的数都减一,问可以获得多少种序列
思路:显然当一个数减少到和其它数相同时,它们可以看做是同一个数了,因为它们在操作中只能同时被减1,因此直接把每个数的单独变动空间乘起来就是答案。
set<int> s;
int main()
{
IOS;
int n;
cin >> n;
for(int i = 1 ; i <= n ; i ++)
{
int x;
cin >> x;
s.insert(x);
}
ll res = 1;
int last = 0;
for(auto x : s)
{
res = res * (x - last + 1) % mod;
last = x;
}
cout << res << endl;
return 0;
}
C题
题意:给你一个长度为n的"WBR"序列,问你按照如下规则最终得到的最顶上元素是什么。
思路:主要是要发觉,当把三个颜色分别看做数字0, 1, 2的时候,假设下面的两个方块是\(a,b\),那么上面的方块将会是\(((-(a + b)) % mod + mod) % mod\)。
依照这个规则向上递推,就能发现其与二项式的系数的关系,就能快速解决了。
int n;
char s[N];
map<char, int> mp;
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;
}
ll C(ll a, ll b, ll p)
{
if(b > a) return 0;
ll res = 1;
for(int i = 1, j = a ; i <= b ; i ++, j --)
{
res = res * j % p;
res = res * qmi(i, p - 2) % p;
}
return res;
}
ll lucas(ll a, ll b, ll p)
{
if(a < p && b < p) return C(a, b, p);
return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
int main()
{
IOS;
cin >> n >> s;
mp['W'] = 0;
mp['B'] = 1;
mp['R'] = 2;
ll res = 0;
for(int i = 0 ; i < n ; i ++)
res += lucas(n - 1, i, mod) * mp[s[i]] % mod;
if(n % 2 == 0) res = -res;
res = (res % mod + mod) % mod;
if(res == 0) cout << "W";
else if(res == 1) cout << "B";
else cout << "R";
return 0;
}
D题
题意:给你一棵树,让你给每一个结点设置一个权值,使得它满足如下条件:
1.任意结点权值 >= 1
2.任意两个结点权值差的绝对值大于等于它们之间的简单(最短)距离
3.在满足1,2条件下,每个结点权值最小
思路:首先要找到树的直径并且进行标记,因为上面有距离最大的点。然后从直径的一端开始进行权值分配,优先分配非直径结点,然后再分配直径结点,注意每次搜到叶子结点或者不能再往下搜索后,权值要+1,只有这样才能满足条件2,不然回溯到直径上的点找下一个点的时候,显然叶子结点和找到的下一个点的权值之差要小于它们的距离。
int h[N], e[M], ne[M], idx;
int res[N], f[N], son[N];
int n, maxd, d, cnt;
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
void dfs1(int u, int fa, int dis)
{
f[u] = fa;
if(dis >= maxd) //等号为了适应 1 号点为直径的一个端点
{
d = u;
maxd = dis;
}
for(int i = h[u] ; ~i ; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
dfs1(j, u, dis + 1);
}
}
void dfs(int u, int fa)
{
res[u] = ++ cnt;
for(int i = h[u] ; ~i ; i = ne[i])
{
int j = e[i];
if(j == fa || j == son[u]) continue;
dfs(j, u);
}
if(son[u])
dfs(son[u], u);
cnt ++;
}
int main()
{
IOS;
cin >> n;
memset(h, -1, sizeof h);
for(int i = 1 ; i < n ; i ++)
{
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
dfs1(1, 0, 0); //找到能从1遍历到的最远的点 d
int s = d; //记录下直径的一个端点
dfs1(s, 0, 0); //找到树的直径
for(int i = d ; i ; i = f[i]) //标记直径上所有的点
son[f[i]] = i;
dfs(s, 0);
for(int i = 1 ; i <= n ; i ++)
cout << res[i] << " ";
return 0;
}