比赛链接：https://www.nowcoder.com/acm/contest/30#question
A：
在acimo星球, tabris 是一名勇敢的屠龙勇士，在上绿岛屠龙前决定挑选N种装备武装自己，现在每种装备有两个，**但每种装备tabris必须选择拿一个**，**不能多也不能少**。
每件装备有自己的属性值，能给tabris属性加成。
对于不同种类的装备之间有叠加效果,如果选择多件装备,最终的属性加成为他们的乘积。
若tabris初始属性值为0，最后属性加成的期望是多少。
每件装备有自己的属性值，能给tabris属性加成。
对于不同种类的装备之间有叠加效果,如果选择多件装备,最终的属性加成为他们的乘积。
若tabris初始属性值为0，最后属性加成的期望是多少。
解法：直接DP算贡献就可以啦。dp[i][0]和dp[i][1]代表到第i种装备选第一个和第二个分别的期望。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1010;
const LL mod = 1e9+7;
int n;
LL a[maxn], b[maxn], dp[maxn][2];
LL qsm(LL a, LL t){
LL ret = 1;
while(t){
if(t&1) ret=ret*a%mod;
a=a*a%mod;
t/=2;
}
return ret;
}
int main(){
while(scanf("%d", &n)!=EOF){
LL ans = 0;
for(int i=1; i<=n; i++){
scanf("%lld%lld", &a[i],&b[i]);
}
memset(dp, 0, sizeof(dp));
dp[1][0]=a[1],dp[1][1]=b[1];
for(int i=2; i<=n; i++){
dp[i][0] = (a[i]*dp[i-1][0]+a[i]*dp[i-1][1])%mod;
dp[i][1] = (b[i]*dp[i-1][0]+b[i]*dp[i-1][1])%mod;
}
ans = (dp[n][0]+dp[n][1])%mod;
//ans = (ans%mod)*qsm(2LL,1LL*n)%mod;
if(ans<0) ans += mod;
ans %= mod;
printf("%lld\n", ans);
}
}B：
tabris实在是太穷了，为了发财，tabris去买了一张彩票，幸运地中了特别奖。
特别奖是这样的，不会直接给你发钱.会给你一串二进制数s，让你在s中选择一个不大于k的区间,这个区间表示的数就是获奖者的奖金数目.
tabris中奖之后已经激动地蒙圈了,他不知道如何选择能获得最多的钱,你能帮帮他不?
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1000010;
char s[maxn];
int main(){
int T, k, ks = 0;
scanf("%d", &T);
while(T--){
scanf("%d", &k);
scanf("%s", s);
int len = strlen(s);
int l = 0, r = 0;
LL ans = 0;
for(;l<len;l++){
while(r<len&&(r-l+1)<k){
r++;
}
LL temp = 0;
for(int i=l; i<=r; i++) temp = temp*2 + (s[i]-'0');
ans = max(ans, temp);
}
printf("Case #%d: %lld\n", ++ks,ans);
}
} tabris有一个习惯，无聊的时候就会数圈圈，无论数字还是字母。
现在tabris更无聊啦，晚上睡不着觉就开始数羊，从a只数到b只。
顺便还数了a到b之间有多少个圈。
但是tabris笨啊，虽然数羊不会数错，但很可能数错圈的个数。
但是tabris很难接受自己笨这个事实，所以想问问你他一共应该数出多少个圈，这样tabris才好判断他到底笨不笨啊。
解法：观察样例发现答案就是l,r区间所有数的出现次数乘上这个数的圈圈的个数的和。由于数据是1e14，所以直接数位DP一下。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int get(int x){
if(x==0||x==4||x==6||x==9) return 1;
else if(x==1||x==2||x==3||x==5||x==7) return 0;
else return 2;
}
LL dp[20][20][20]; //dp[pos][num][sum]前pos位，num已经出现了sum次
LL digit[20];
LL dfs(int pos, int num, int sum, bool lead, bool limit){
if(pos==0) return sum;
if(!limit&&!lead&&dp[pos][num][sum]!=-1) return dp[pos][num][sum];
int up=limit?digit[pos]:9;
LL ans=0;
if(!lead||pos==1) ans+=dfs(pos-1, num, sum+(num==0), 0, limit&&digit[pos]==0);
else ans+=dfs(pos-1, num, sum, 1, limit&&digit[pos]==0);
for(int i=1; i<=up; i++){
ans+=dfs(pos-1, num, sum+(num==i), 0, limit&&digit[pos]==i);
}
if(!limit&&!lead) dp[pos][num][sum]=ans;
return ans;
}
LL f(LL x, int num){
if(x<0) return 0;
if(x==0) return num==0?1:0;
int pos=0;
while(x){
digit[++pos]=x%10;
x/=10;
}
return dfs(pos,num,0,1,1);
}
int main(){
int T;
LL a, b;
scanf("%d", &T);
memset(dp, -1, sizeof(dp));
while(T--){
LL ans = 0;
scanf("%lld%lld", &a,&b);
for(int i=0;i<=9;i++) ans+=(f(b,i)-f(a-1,i))*get(i);
printf("%lld\n", ans);
}
}G：
幼儿园的孩子们正在做游戏，每个人都有自己的帮派，帮派之间打架，然后赢者吞并弱者扩大自己的势力。最开始每个孩子的帮派中只有自己，然后接下来有会有两个人打架，这两个人会集结自己所属的势力开始打架，打赢的一方就会吞并输的一方，当然如果x，y是一个势力就不会打起来。有些聪明的小朋友会将自己的糖分给其他小朋友引诱他离开所属势力加入到自己势力。又有一些小朋友会对现在的势力不满，然后反叛出去自立门户。
作为打架的双方，只有人数大于另一方才能打赢。即：人数相等则没有输赢，两个帮派没有变化。
幼儿园里面共有N个孩子，接下来有M次操作，操作有如下4种
1) query 查询现在有多少个势力。
2) fight x y 表示x，y打架.并输出"z is winner!"胜利的一方(z是x或y),如果没有打平则输出"Either is winner!".如果x,y属于同一个势力不会打架,当然也不用输出.
3) tempt x y 表示x诱惑y、将y拉入x的势力。
4) revolt x 表示x反叛，（自立门户）
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000010;
int n, m, cnt, ans, num[maxn], fa[maxn], Rank[maxn];
int find_set(int x){
if(x==fa[x]) return x;
else return fa[x] = find_set(fa[x]);
}
void del(int x){
int fx = find_set(num[x]);
if(Rank[fx]==1) return;
Rank[fx]--;
num[x] = ++cnt;
fa[num[x]] = num[x];
Rank[num[x]]=1;
ans++;
}
int main(){
int T;
int ks = 0;
scanf("%d", &T);
while(T--){
scanf("%d%d", &n,&m);
for(int i=1; i<=n; i++) fa[i]=i,num[i]=i,Rank[i]=1;
string op;
ans = n;
cnt = n;
printf("Case #%d:\n", ++ks);
while(m--){
cin >> op;
if(op=="query"){
printf("%d\n", ans);
}
else if(op=="fight"){
int x, y;
scanf("%d%d", &x,&y);
int fx = find_set(num[x]);
int fy = find_set(num[y]);
if(fx == fy) continue;
if(Rank[fx]>Rank[fy]){
printf("%d is winner!\n", x);
fa[fy] = fx;
Rank[fx] += Rank[fy];
Rank[fy] = 0;
ans--;
}else if(Rank[fx]<Rank[fy]){
fa[fx] = fy;
Rank[fy] += Rank[fx];
Rank[fx] = 0;
ans--;
printf("%d is winner!\n", y);
}else{
printf("Either is winner!\n");
}
}
else if(op=="tempt"){
int x,y;
scanf("%d%d", &x,&y);
int fx = find_set(num[x]);
del(y);
int fy = find_set(num[y]);
if(fx ==fy) continue;
fa[fy] = fx;
Rank[fx] += Rank[fy];
Rank[fy] = 0;
ans--;
}
else if(op=="revolt"){
int x;
scanf("%d", &x);
int fx = find_set(num[x]);
if(Rank[fx]==1) continue;
Rank[fx]--;
num[x] = ++cnt;
fa[num[x]] = num[x];
Rank[num[x]]=1;
ans++;
}
}
}
}C：
小明很喜欢打游戏，现在已知一个新英雄即将推出，他同样拥有四个技能，其中三个小技能的释放时间和固定的伤害值为：
1.乌鸦坐飞机 释放时间：x 固定伤害值：a
2.蜘蛛吃耳屎 释放时间：y 固定伤害值：b
3.饿狼前进 释放时间：z 固定伤害值：c
他还有一个大招，其释放的时间是一个区间【L,R】，可以在区间内任意时间点释放出技能，其如果在L+i时刻释放技能，其能够打出的伤害值为:temp+A*i
这里temp值表示技能的基础伤害（同时也就是在时刻L释放技能的伤害值）,A是一个常数。
小明很喜欢研究连招使得在有限的时间内打出最高的伤害，现在他想要在T长度单位时间内打出最高的伤害，问这个最大伤害值。
线段树加DP，可以看到前面3个技能可以直接递推，但是大招不能直接递推，我们需要找一个可行区间的最大值去递推，所以需要维护一个支持单点更新，区间查询的数据结构，这个线段树就可以搞定。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 100010;
LL dp[maxn];
struct node
{
LL l, r;
LL maxx;
} Tree[maxn * 4];
void push_up(LL rt)
{
Tree[rt].maxx = max(Tree[rt << 1].maxx, Tree[rt << 1 | 1].maxx);
}
void build(LL l, LL r, LL rt)
{
Tree[rt].maxx = 0;
Tree[rt].l = l;
Tree[rt].r = r;
if (l == r) return;
LL mid = (l + r) / 2;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
push_up(rt);
}
void update(LL pos, LL val, LL rt)
{
if (Tree[rt].l == Tree[rt].r)
{
Tree[rt].maxx = val;
return;
}
LL mid = (Tree[rt].l + Tree[rt].r) / 2;
if (pos <= mid) update(pos, val, rt * 2);
else update(pos, val, rt * 2 + 1);
push_up(rt);
}
LL query(LL L, LL R, LL rt)
{
if (L <= Tree[rt].l && Tree[rt].r <= R) return Tree[rt].maxx;
LL mid = (Tree[rt].l + Tree[rt].r) / 2;
LL ret = -__LONG_LONG_MAX__;
if (L <= mid) ret = max(ret, query(L, R, rt << 1));
if (mid < R) ret = max(ret, query(L, R, rt << 1 | 1));
return ret;
}
int main()
{
LL n, x, a, y, b, z, c, L, R, temp, A;
LL t;
while (~scanf("%lld", &n))
{
scanf("%lld%lld", &x, &a);
scanf("%lld%lld", &y, &b);
scanf("%lld%lld", &z, &c);
scanf("%lld%lld%lld%lld", &L, &R, &temp, &A);
build(0, n, 1);
for (LL i = 1; i <= n; i++)
{
t = dp[i - 1];
if (i >= x) t = max(t, dp[i - x] + a);
if (i >= y) t = max(t, dp[i - y] + b);
if (i >= z) t = max(t, dp[i - z] + c);
LL ll = i - R, rr = i - L;
if (ll < 0) ll = 0;
if (i >= L) t = max(t, query(ll, rr, 1) + temp + 1LL * i * A - 1LL * L * A);
dp[i] = t;
update(i, t - 1LL * i * A, 1);
}
printf("%lld\n", dp[n]);
}
}E：
给出一个序列，你的任务是求每次操作之后序列中 （a[j]-a[i]）/（j-i）【1<=i<j<=n 】的最大值。
操作次数有Q次，每次操作需要将位子p处的数字变成y.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
double maxx[maxn*4];
double a[maxn];
void push_up(int rt){
maxx[rt] = max(maxx[rt<<1], maxx[rt<<1|1]);
}
void build(int l, int r, int rt){
if(l==r){
maxx[rt] = a[l+1]-a[l];
return;
}
int mid=(l+r)/2;
build(l, mid, rt<<1);
build(mid+1, r, rt<<1|1);
push_up(rt);
}
void update(int pos, double val, int l, int r, int rt){
if(l==r){
maxx[rt] = val;
return;
}
int mid=(l+r)/2;
if(pos<=mid) update(pos, val, l, mid, rt*2);
else update(pos, val, mid+1, r, rt*2+1);
push_up(rt);
}
int query(int L, int R, int l, int r, int rt){
if(L<=l&&r<=R) return maxx[rt];
int mid = (l+r)/2;
if(R<=mid) return query(L, R, l, mid, rt*2);
else if(L>mid) return query(L, R, mid+1, r, rt*2+1);
else return max(query(L, mid, l, mid, rt*2) , query(mid+1, R, mid+1, r, rt*2+1));
}
int main(){
int n, q;
while(~scanf("%d", &n)){
for(int i=1; i<=n; i++) scanf("%lf", &a[i]);
build(1, n-1, 1);
scanf("%d", &q);
while(q--){
int x, y;
scanf("%d %d", &x,&y);
a[x] = y;
if(x!=n) update(x,a[x+1]-a[x],1,n-1,1);
if(x!=1) update(x-1,a[x]-a[x-1],1,n-1,1);
printf("%d.00\n", (int)maxx[1]);
}
}
} H：
给一个有根二叉树,可以无限次的交换任意节点的左右子树,问最少交换多少次使得该树的中序遍历的字典序最小?
解法：DFS。细节见代码。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
int ls[maxn], rs[maxn];
int ans = 0, flag, n, rt;
int dfs(int u)
{
if (ls[u] && rs[u])
{
int l = dfs(ls[u]);
int r = dfs(rs[u]);
if (l > r)
{
swap(ls[u], rs[u]);
++ans;
}
return min(l, r);
}
else if (ls[u])
{
int l = dfs(ls[u]);
if (l > u)
{
swap(ls[u], rs[u]);
++ans;
}
return min(l, u);
}
else if (rs[u])
{
int r = dfs(rs[u]);
if (r < u)
{
swap(ls[u], rs[u]);
++ans;
}
return min(r, u);
}
else return u;
}
void print(int u)
{
if (ls[u]) print(ls[u]);
if (flag) putchar(' ');
else flag = 1;
printf("%d", u);
if (rs[u]) print(rs[u]);
}
int main()
{
while (~scanf("%d%d", &n, &rt))
{
for (int i = 1; i <= n; i++) scanf("%d%d", &ls[i], &rs[i]);
flag = 0;
dfs(rt);
printf("%d\n", ans);
print(rt);
puts("");
}
} F：
从小老师就教育我们，一根筷子容易折断，而一捆筷子不容易折断。
因为要出战世界杯，我们需要考虑派一只队伍出战，而我们希望出战的队伍的团结力最大。
而一个队伍的团结力取决于每个人的性格，每个人都有一个性格基因【（由字符串表示），比如小明的性格基因为：abbcde】，性格基因的排列方式是可以通过一个人的后天培养而改变的，其改变方式就是类似于循环，【小明的性格基因为：abbcde，他可以变成：bbcdea，bcdeab，cdeabb，deabbc，eabbcd】 。
一个队伍中如果最多有x个人的性格基因可以完全相等的话，那么这个队伍的团结力就是x。
比如一个队伍有五个人：
小明：abbcde
小红：bbcdea
大明：cdeabb
大红：efg
小紫：fge
明显小明小红和大明的性格基因可以变成相等的，大红和小紫的性格基因可以变成相等的， 这个 最多有3个人的性格基因可以完全相等的，所以这个五人队伍的团结力就是3；
现在已知可以出战的人数为n个，每个人都有一个性格基因字符串，而作为一只队伍出战的话，需要队伍中的每个人都互相达成共识。同时也已知m个信息，每个信息是：
a想要和b一起出战【注意，这里只是a的一厢情愿】，只有当a想要和b一起出战，并且b也想要和a一起出战的时候，两个人才能一起出战。想要一起出战是可以具有传递性的，比如a想要和b一起出战，b想要和c一起出战的话，那么a也可以想要和c一起出战。
我们肯定希望派出的队伍的团结力最大，请计算出这个最大团结力。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
const LL Base[2]={121,131};
const LL Mod[2]={1000000007,1000000009};
int MinmalRep(char *s){
int i=0,j=1,k=0,f,l=strlen(s);
while(i<l&&j<l&&k<l){
f=s[(i+k)%l]-s[(j+k)%l];
if(!f)k++;
else{
if(f>0)i=i+k+1;
else j=j+k+1;
if(i==j)i++;
k=0;
}
}
return min(i,j);
}
char buf[maxn];
LL val[maxn];
//Tarjan
vector <int> G[maxn], s[maxn];
int low[maxn], dfn[maxn], Stack[maxn];
bool inStack[maxn];
int dfsclk,top,scc;
void Tarjan(int u){
low[u]=dfn[u]=++dfsclk;
Stack[top++]=u;
inStack[u]=1;
for(auto &v:G[u]){
if(!dfn[v]){
Tarjan(v);
low[u] = min(low[u], low[v]);
}else if(inStack[v]){
low[u] = min(low[v], dfn[v]);
}
}
if(low[u]==dfn[u]){
scc++;
int now;
do{
now=Stack[--top];
inStack[now]=0;
s[scc].push_back(now);
}while(now!=u);
}
}
void solve(int n){
for(int i=1;i<=n;i++) dfn[i]=inStack[i]=0;
dfsclk=top=scc=0;
for(int i=1; i<=n; i++) if(!dfn[i]) Tarjan(i);
}
int main(){
int n,m;
while(~scanf("%d%d", &n,&m)){
for(int i=0; i<maxn; i++) G[i].clear();
for(int i=0; i<maxn; i++) s[i].clear();
for(int i=1;i<=n;i++){
scanf("%s", buf);
int len=strlen(buf),loc=MinmalRep(buf);
LL has[2]={0,0};
for(int j=0;j<len;j++){
int t=buf[(j+loc)%len]-'a'+1;
for(int k=0;k<2;k++){
has[k]=(has[k]*Base[k]+t)%Mod[k];
}
}
val[i]=has[0]*Base[0]+has[1];
}
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
G[x].push_back(y);
}
solve(n);
int ans=0;
for(int i=1;i<=scc;i++){
unordered_map<LL,int>cnt;
for(auto &t:s[i]) cnt[val[t]]++;
for(auto t:cnt) ans = max(ans,t.second);
}
printf("%d\n", ans);
}
}I：
解法：开始真不知道这个表达式表达了啥意思，知道看了Q神的代码，发现根本不需要懂这表达了啥，实际上就是类似于做了个圆周卷积，然后这个圆周卷积再做m次，一次一次的做太慢，考虑类似于快速幂那样来做就OK啦，模仿Q巨写法。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 202;
const int mod = 1e9+7;
void add(int &x, int y){
x += y;
if(x>=mod) x%=mod;
}
int a[maxn],b[maxn],c[maxn];
void mul(int f[],int g[],int len){
int tmp[maxn];
for(int i=0;i<len;i++) tmp[i]=0;
for(int i=0;i<len;i++)
for(int j=0;j<len;j++)
add(tmp[(i+j)%len],1LL*f[i]*g[j]%mod);
for(int i=0;i<len;i++) f[i]=tmp[i];
}
int main(){
int T,n,m,k;
scanf("%d", &T);
while(T--){
scanf("%d%d%d", &n,&m,&k);
for(int i=0;i<n;i++) scanf("%d", &a[i]);
for(int i=0;i<n;i++) b[i]=i==0;
for(int i=0;i<n;i++){
int d=min(i,n-i);
c[i]=(d>0&&d<k)*(k-d);
}
while(m){
if(m&1) mul(b,c,n);
mul(c,c,n);
m/=2;
}
mul(a,b,n);
for(int i=0;i<n;i++){
if(i==0) printf("%d", a[i]);
else printf(" %d", a[i]);
}
printf("\n");
}
}J：
这个求原函数和导函数需要去学一学高数了，我现在已经是数学渣了。orz
#include <bits/stdc++.h>
using namespace std;
const int M=55;///公式的精度为O(1/(100*M^4))要造数据时把M调到1000 即可有10^-14的精度
const double e=exp(1);
int c;
inline double F( double x)//原函数
{
return 0.5*(log(x+e*c/x)+log(x));
}
inline double D( double x)//导函数
{
return 1/(x*x+c*e)-2.0/((x+c*e/x)*(x+c*e/x));
}
inline double fun(int n)
{
int i;
double ans=0,l=0.5,r=0.5+n,u;
if(c<2000||n<=M)
{
l+=M;
for(i=1; i<=M&&i<=n; i++)
{
ans+=i/(i*i+c*e);
}
}
if(n>M)
ans+=F(r)-F(l)-(D(r)-D(l))/24.0;
return ans;
}
int main()
{
int n,q,i;
double sum;
while(scanf("%d%d",&n,&c)!=EOF)
{
printf("%.10f\n",fun(n));
}
return 0;
}
后话：星期四出发去ECfinal了，这次必定打铁(逃~~~)
京公网安备 11010502036488号