北京信息科技大学第十二届程序设计竞赛暨ACM选拔赛（同步赛）
A-爱丽丝的人偶（一）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 998244353 ;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
int main()
{
int n;
cin >> n;
int j = n/2,k = n;
int t = 1;
for(int i = n; i >= 1; i--){
if(t&1) cout << k << " ",k--;
else cout << j << " ",j--;
t++;
}
return 0;
}
B-爱丽丝的人偶（二）：排列组合+快速幂
思路：因为要k个不同的数，那就先统计不同的数有多少个，然后从这些数中取k个数，用set求。注意k大于不同数的个数时，答案为零。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const ll mod = 1e9+7;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
ll qpow(ll a,ll b){
ll res = 1;
while(b){
if(b&1) res = res*a%mod;
a = a*a%mod;
b >>= 1;
}
return res%mod;
}
set<ll>s;
ll a[100005];
int main()
{
ll n,m,k;
cin >> n >> k;
for(ll i = 1; i <= n; i++){
cin >> a[i];
s.insert(a[i]);
}
ll num = s.size();
if(num < k) cout << 0;
else{
ll mm = max(num-k,k);
ll nn = min(num-k,k);
//cout << mm << nn << endl;
ll s = 1,x = 1;
for(ll i = num; i > mm; i--){
s = (s*1ll*i)%mod;
}
for(ll i = 1; i <= nn; i++){
x = (x*1ll*i)%mod;
}
x = qpow(x,mod-2);
cout << s*x%mod;
}
return 0;
} C-打毛玉大赛：简单博弈
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 998244353 ;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
int main()
{
int n,m,k;
cin >> n >> m;
if((n == 1 && m == 2) || (n == 2 && m == 1)) cout << "A";
else cout << "B";
return 0;
}
D-贪玩的二小姐(续)：栈
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
ll dp[100005][3];
int a[100005];
int main()
{
int n,x;
cin >> n;
cin >> a[1] >> a[2];
for(int i = 3; i <= n; i++){
cin >> a[i];
dp[i][0] = max(dp[i-1][1],dp[i-1][0]);
dp[i][1] = dp[i-2][0]+a[i-1];
}
cout << max(dp[n][1],dp[n][0]) << endl;
return 0;
} E-游戏机本当下手
思路：先将原串按连续相同的子串分段，即压缩成类似于101010....这样的串，而我们可以发现，如果要通过按k次得到某个串，我们只需要考虑压缩后串的子串长度为k的两端的长度，中间的长度是不需要考虑的，所有对于压缩后的串，我们从1开始枚举，直至找不到长度为k的串为止，那么能够通过k次找的子串为a[i]*a[i+k-1] , 最后求和即可，特别要考虑k==1的情况。直接看例子，比如 111000，k=1，对于第一段 111，可以有 1,1,1,11,111,11, 即（1+3-1）*（3-1）/ 2 + 3，3为改段的长度，所有k=1的情况，每段可以找到的子串为，(1+a[i]-1)*(a[i]-1)/2+a[i]. 以上a[i]代表每一段的长度。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 20000311;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
char s[1000005];
ll a[1000005],cnt = 0;
int main()
{
int n,k;
memset(a,0,sizeof a);
scanf("%d%d",&n,&k);
scanf("%s",s);
for(int i = 0; i < n; i++){
int j;
cnt++;
for(j = i; j < n; j++){
if(s[i] == s[j]) a[cnt]++;
else break;
}
i = j - 1;
}
ll sum = 0;
if(k == 1){
for(int i = 1; i <= cnt; i++){
sum += a[i];
sum += (1+a[i]-1)*(a[i]-1)/2;
}
}
else{
for(int i = 1; i <= cnt; i++){
if(i+k-1 > cnt) break;
sum += (a[i]*a[i+k-1]);
}
}
printf("%lld\n",sum);
return 0;
} F-宵暗的妖怪：dp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
ll dp[100005][3];
int a[100005];
int main()
{ int n,x; cin >> n; cin >> a[1] >> a[2]; for(int i = 3; i <= n; i++){
cin >> a[i];
dp[i][0] = max(dp[i-1][1],dp[i-1][0]);
dp[i][1] = dp[i-2][0]+a[i-1];
}
cout << max(dp[n][1],dp[n][0]) << endl; return 0;
}
G-魔界伊始：gcd/更相减损法
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 20000311;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
ll a[100005];
ll gcd(ll x,ll y)
{
return y == 0?x:gcd(y,x%y);
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
ll ans = a[1];
for(int i = 2; i <= n; i++){
ans = gcd(ans,a[i]);
}
int q;
cin >> q;
ll x;
while(q--){
cin >> x;
if(x%ans) cout << "No" << endl;
else cout << "Yes" << endl;
}
return 0;
} H-芭芭拉冲鸭~：树的直径dp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 20000311;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
char s[100005];
vector<int>a[100005];
int ans = 0;
int dp[100005];
void dfs(int so,int fa)
{
int l = a[so].size();
for(int i = 0; i < l; i++){
int v = a[so][i];
if(v == fa) continue;
dfs(v,so);
if(s[so] == s[v]){
ans = max(ans,dp[so]);
}
else{
ans = max(ans,dp[so]+dp[v]+1);
dp[so] = max(dp[so],dp[v]+1);
}
}
}
int main()
{
int n;
scanf("%d",&n);
scanf("%s",s+1);
for(int i = 1; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
}
dfs(1,0);
printf("%d",ans);
return 0;
} I-永远亭的小游戏
注意取模
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const ll mod = 1e9+7;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
ll qpow(ll a,ll b)
{
ll res = 1;
a %= mod;
while(b)
{
if(b&1) res = res*a%mod;
a = a*a%mod;
b >>= 1;
}
return res%mod;
}
int main()
{
ll n,m,k,x;
ll sum1 = 0,sum2 = 0,sum3 = 0,b;
scanf("%lld%lld%lld",&n,&m,&k);
for(int i = 1; i <= n; i++) scanf("%lld",&x),sum1 = (sum1+x)%mod;
for(int i = 1; i <= m; i++) scanf("%lld",&x),sum2 = (sum2+x)%mod;
for(int i = 1; i <= k; i++) scanf("%lld",&x),sum3 = (sum3+x)%mod;
sum1 = (sum1%mod*sum2%mod)%mod*sum3%mod;
b = (n%mod*m%mod)%mod*k%mod;
b = qpow(b,mod-2);
cout << (sum1%mod*b%mod)%mod;
return 0;
} K-玩具销售员：贪心
https://ac.nowcoder.com/acm/contest/8755/K 思路：每次取的两个都取次品，看需要多少次。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 998244353 ;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
int main()
{
int n,m,k;
cin >> n >> m >> k;
int cs,ys;
cs = m/2;
ys = m%2;
if(cs+ys > k) cout << "No";
else cout << "Yes";
return 0;
} 
