10.1 Morning
Problem A. calculator
【题目描述】
现在你手里有一个计算器,上面显示了一个数S。这个计算器非常奇怪,它只有两个按钮,分别可以把屏幕上显示的数值加上1或者减去1。并且,如果计算器屏幕上的数变成了负数,那么计算器就会损坏。现在你想要在K次操作之内把屏幕上的数字变成T,而且不让计算器损坏,求一个有多少种方案。 对10^9+7取模。
两种方案不同当且仅当按钮被按下的序列不同。
【输入描述】
一行三个整数S,T,K
【输出描述】
一行一个正整数,表示答案
【输入输出样例】
【input】
0 1 3
【output】
3
【样例解释】
一共有3种可能的操作序列
+1;
+1,-1,+1;
+1,+1,-1
【数据范围】
对于30%的数据，S,T,K<=10
对于60%的数据，S,T,K<=1000
对于100%的数据，0<=S,T,K<=100000
【题解】
【代码实现】
30分代码（考场代码）
#include<cstdio>
#define mod 1000000007
long long s,t,k,ans;
void dfs(long long pos,long long tot)
{
if(pos==t) ans=(ans+1)%mod;
if(tot>=k) return;
dfs(pos+1,tot+1);
if(pos>0) dfs(pos-1,tot+1);
}
int main()
{
freopen("calculator.in","r",stdin);
freopen("calculator.out","w",stdout);
scanf("%lld%lld%lld",&s,&t,&k);
dfs(s,0);
printf("%lld",ans%mod);
fclose(stdin);
fclose(stdout);
return 0;
}60分代码（!wyxdrqc大佬的代码）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
const int N = 4e3 + 4;
LL f[N][N];
LL s,t,k;
inline LL dfs(LL now,LL last){
if(abs(now - t) > k - last) return 0;
if(now < 0) return 0;
if(f[now][last]) return f[now][last];
if(now != t)
f[now][last] = (dfs(now + 1,last + 1) + dfs(now - 1,last + 1))%mod;
else f[now][last] = (dfs(now + 1,last + 1) + dfs(now - 1,last + 1) + 1)%mod;
return f[now][last];
}
int main(){
freopen("calculator.in","r",stdin);
freopen("calculator.out","w",stdout);
cin >> s >> t >> k;
f[t][k] = 1;
cout << dfs(s,0) << endl;
return 0;
}100分代码（std）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = (int)2e5, mod = (int)1e9 + 7;
typedef long long ll;
int S, T, K;
int fac[N + 10], ifac[N + 10];
int pow(int x, int y) {
ll t = x, r = 1;
for ( ; y; y >>= 1, t = t * t % mod)
if (y & 1) r = r * t % mod;
return r;
}
void preprocessing() {
fac[0] = 1;
for (int i = 1; i <= N; ++i) fac[i] = (ll)fac[i - 1] * (ll)i % mod;
ifac[N] = pow(fac[N], mod - 2);
for (int i = N - 1; i >= 0; --i) ifac[i] = (ll)ifac[i + 1] * (ll)(i + 1) % mod;
}
int c(int n, int r) {
return (ll)fac[n] * (ll)ifac[r] % mod * (ll)ifac[n - r] % mod;
}
int main() {
freopen("calculator.in", "r", stdin);
freopen("calculator.out", "w", stdout);
preprocessing();
scanf("%d %d %d", &S, &T, &K);
if (S > T) swap(S, T);
int ans = 0;
for (int i = 0; i <= K; ++i) {
if ((i + T - S) & 1) continu
int x = (i - T + S) >> 1, y = (i + T - S) >> 1;
if (x < 0) continue;
(ans += c(x + y, x)) %= mod;
if (x > S) (ans += (mod - c(x + y, x - S - 1))) %= mod;
}
printf("%d\n", ans);
return 0;
}Problem B. work
【题目描述】
有一个工厂一共有m台排成一排的机器,其中第台机器的工作效率是e[i]。
机器有开或者关两种状态,显然当所有机器都开着的时候工作效率可以达到最大。但是由于工厂的供电系统岀现了故障,不能够同时开启仼意连续k+1台机器,否则工厂就会爆炸。
求工厂在不发生爆炸的前提下能够达到的最大效率。
【输入描述】
第一行两个正整数n和k。
接下来n行,每一行一个正整数,代表e[i]。
【输出描述】
一行一个数表示答案。
【输入输出样例】
【input】
5 2
1 2 3 4 5
【output】
12
【数据范围】
对于30%的数据，1<=n<=100
对于100%的数据，1<=n<=100000,1<=k,0<=e[i]<=10^9
【题解】
【代码实现】
30分代码
#include<iostream>
#include<cstdio>
using namespace std;
int a[101];
long long f[101][101];
int main ()
{
freopen("work.in","r",stdin);
freopen("work.out","w",stdout);
int n,k,i,j;
scanf("%d%d",&n,&k);
for(i=1;i<=n;++i) scanf("%d",&a[i]);
f[1][1]=a[1];f[1][0]=0;
for(i=2;i<=n;++i)
f[1][i]=-1;
for(i=2;i<=n;++i)
{
for(j=1;j<=k;++j)
if(f[i-1][j]>f[i][0]) f[i][0]=f[i-1][j];
for(j=1;j<=k;++j)
{
if(f[i-1][j-1]!=-1) f[i][j]=f[i-1][j-1]+a[i];
else f[i][j]=-1;
}
}
long long sum=0;
for(i=1;i<=k;++i)
if(f[n][i]>sum) sum=f[n][i];
cout<<sum<<endl;
fclose(stdin);fclose(stdout);
return 0;
}100分代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = (int)1e5;
typedef long long ll;
typedef int arr[N + 10];
int n, K, f, r;
arr q;
ll e[N + 10], dp[N + 10];
int main() {
freopen("work.in", "r", stdin);
freopen("work.out", "w", stdout);
scanf("%d %d", &n, &K);
for (int i = 1; i <= n; ++i) scanf("%lld", e + i), e[i] += e[i - 1];
q[f = r = 1] = 0, dp[0] = 0;
for (int i = 1; i <= n + 1; ++i) {
if (q[f] < i - K - 1) ++f;
dp[i] = dp[q[f]] + e[i - 1] - e[q[f]];
for ( ; r >= f && dp[q[r]] - e[q[r]] <= dp[i] - e[i]; --r);
q[++r] = i;
}
cout << dp[n + 1] << endl;
return 0;
}Problem C. cubes
【题目描述】
约翰和贝西在叠积木。共有30000块积木，编号为1到30000。一开始，这些积木放在地上，自然地分成N堆。贝西接受约翰的指示，把一些积木叠在另一些积木的上面。一旦两块积木相叠， 彼此就再也不会分开了，所以最后叠在一起的积木会越来越高。约翰让贝西依次执行P条操作，操作分为两种：
第一种是移动操作，格式为“移动X到Y的上面”。X和Y代表两块积木的编号，意思是将X所的那堆积木，整体叠放到Y所在的那堆积木之上；
第二种是统计操作，格式为“统计Z下方的积木数量”。Z代表一块积木的编号，意思是贝西需要报告在编号为Z的积木之下还有多少块积木
请编写一个程序，帮助贝西回答每条统计问题。
【输入格式】
第一行：单个整数：P，1 ≤ P ≤ 10^5
第二行到第P + 1行：每行描述一条命令，如果这行开头的字母是 M，代表一条移动命令，后面的两个整数代表上文中的X和Y；如果开头字母是 C，代表一条统计命令。后面的整数代表上文中的Z，保证所有的移动命令都有意义，X和Y不会已经出现在同一堆积木里
【输出格式】
对每一个统计命令，输出正确回答，用换行符分开每个查询的结果
【输入输出样例】
【input】
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
【output】
1
0
2
【数据范围】
对于40%的数据，m<=200
对于100%的数据，m<=100000
【题解】
【代码实现】
40分暴力
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define RI register int
using namespace std;
typedef long long ll;
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
const int INF = 1e9 + 7;
const int MAXN = 100000 + 5;
inline void read(int &x)
{
x = 0;
bool flag = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') flag = 1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
if(flag) x *= -1;
}
char s[5];
int m,a,b,tot = 0,ans;
map <int,bool> use;
map <int,int> num;
int son[MAXN],fa[MAXN],tmp;
int find(int a)
{
while(son[a] != -1)
a = son[a];
return a;
}
int findf(int a)
{
while(fa[a] != -1)
a = fa[a];
return a;
}
int main()
{
freopen("cubes.in","r",stdin);
freopen("cubes.out","w",stdout);
read(m);
for(int i = 1;i <= m;i ++)
{
scanf("%s",s + 1);
if(s[1] == 'M')
{
read(a),read(b);
if(!use[a])
{
num[a] = ++ tot;
use[a] = 1;son[tot] = -1,fa[tot] = -1;
}
if(!use[b])
{
num[b] = ++ tot;
use[b] = 1;son[tot] = -1,fa[tot] = -1;
}
if(findf(num[a]) == findf(num[b])) continue;
a = find(num[a]),b = findf(num[b]);
son[a] = b;fa[b] = a;
}
else
{
read(a);
if(!use[a])
{
num[a] = ++ tot;
use[a] = 1;son[tot] = -1;
}
ans = 0,tmp = num[a];
while(son[tmp] != -1)
{
tmp = son[tmp];
ans ++;
}
cout << ans << endl;
}
}
fclose(stdin);
fclose(stdout);
return 0;
}100分正解
#include <bits/stdc++.h>
using namespace std;
const int N = (int)3e4;
typedef int arr[N + 10];
typedef long long ll;
int m, j, k;
arr ufs, below, sz;
char ope[3];
int find(int x) {
if (x == ufs[x]) return x;
int f = find(ufs[x]);
below[x] += below[ufs[x]];
return ufs[x] = f;
}
void move(int x, int y) {
int fx = find(x), fy = find(y);
ufs[fx] = fy;
below[fx] += sz[fy];
sz[fy] += sz[fx];
}
int main() {
freopen("cubes.in", "r", stdin);
freopen("cubes.out", "w", stdout);
for (int i = 1; i <= N; ++i) ufs[i] = i, sz[i] = 1, below[i] = 0;
for (scanf("%d", &m); m--; ) {
scanf("%s", ope + 1);
if (ope[1] == 'M') {
scanf("%d %d", &j, &k), move(j, k);
}
else {
scanf("%d", &k);
ufs[k] = find(k);
printf("%d\n", below[k]);
}
}
return 0;
}