符号约定及其他说明：C(m,n) 表示从 n 个不同元素中取出 m 个元素的所有组合的个数; n&1 == n%2 .
A.赢的次数( https://ac.nowcoder.com/acm/contest/11223/A ) ：
1.思路：
比赛情况可以表示为 (0/1,0/1,0/1,...,0/1) ，其中恰好有 k 个 1 (即 Alice 赢 k 次) 的情况有 C(k,n) 种，题目即求其最大值。
联系到二项式定理及杨辉三角，可以发现最中间的组合数最大(超几何分布也印证了这一点)，即：
n 为偶数，max{k} = n / 2 ；n 为奇数，max{k} = n / 2 或 n / 2 + 1.
时间复杂度 O(1).
2.代码：
#include<cstdio>
using namespace std;
int main(){
int n;
scanf("%d",&n);
if(n&1) printf("%d %d",n/2,n/2+1);
else printf("%d",n/2);
return 0;
} 1.思路：
考虑其逆命题：无论如何 排列这个序列都存在长度小于等于 2 的子区间和等于 0.
若存在 0，直接特判;
若不存在 0 ，考虑把相同的数放在一起构成若干集合，则为了使其逆命题成立，必须整个数列只由对应数和为0的两个集合组成(因为一旦多出若干个数，就可以插到这两个集合之间，由于不存在0，也就不存在相邻两个数相加为0了)。
因此排一下序(相当于 把相同的数放在一起)，判一下开头和结尾以及这两个集合的长度之和是否等于总长即可.
时间复杂度 O(nlogn).
2.代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5e5+10;
int n,a[N];
bool flag=1;
inline int read(){
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=getchar(); }
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
inline void write(int x){
if(x<0){ putchar('-'); x=-x; }
if(x>9) write(x/10);
putchar(x%10+'0');
}
int count(int t){
int cnt=0;
for(int i=1;i<=n;++i)
if(a[i]==t) ++cnt;
return cnt;
}
int main(){
n=read();
for(int i=1;i<=n;++i){
a[i]=read();
if(a[i]==0) flag=0;
}
sort(a+1,a+n+1);
if(flag&&a[1]+a[n]==0&&count(a[1])+count(a[n])==n) flag=0;
if(flag) printf("YES");
else printf("NO");
return 0;
} 1.思路：
先用 STL map 的查重功能给每个字符串分配一个整数编号(类似离散化)，题目即为查询 a[ i - k - 1 ] ~ a[ i - 1 ] 中 a [ i ] 出现的次数。
蒟蒻太弱了，没看出来答案的单调性，直接莽了一颗可持久化权值线段树(主席树)上去就没了......(毕竟相当于模板题[区间第 k 小]去掉树上二分).
并且蒟蒻懒得写同步历遍，前缀和相减常数略大.
最后，别忘开 long long .
时空复杂度均为 O(nlogn).
2.代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,LG=24;
int n,a[N],k,num,ans,rts[N],cnt=1;
map<string,int> mp;
struct Node{
int val;
int lc,rc;
}tr[N*LG];
inline int read(){
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=getchar(); }
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
inline void write(int x){
if(x<0){ putchar('-'); x=-x; }
if(x>9) write(x/10);
putchar(x%10+'0');
}
void Build(int l=1,int r=n,int p=1){
if(l==r) return;
tr[p].lc=++cnt,tr[p].rc=++cnt;
int mid=l+((r-l)>>1);
Build(l,mid,tr[p].lc),Build(mid+1,r,tr[p].rc);
}
void Update(int x,int l,int r,int p,int q){
if(l==r) tr[q].val=tr[p].val+1;
else{
tr[q].lc=tr[p].lc,tr[q].rc=tr[p].rc;
int mid=l+((r-l)>>1);
if(x<=mid) tr[q].lc=++cnt,Update(x,l,mid,tr[p].lc,tr[q].lc);
else tr[q].rc=++cnt,Update(x,mid+1,r,tr[p].rc,tr[q].rc);
tr[q].val=tr[tr[q].lc].val+tr[tr[q].rc].val;
}
}
int Query(int l,int r,int cl,int cr,int p){
if(cl>r||cr<l) return 0;
else if(cl>=l&&cr<=r) return tr[p].val;
else{
int mid=cl+((cr-cl)>>1);
return Query(l,r,cl,mid,tr[p].lc)+Query(l,r,mid+1,cr,tr[p].rc);
}
}
signed main(){
n=read(),k=read();
for(int i=1;i<=n;++i){
string s;
cin>>s;
auto it=mp.find(s);
if(it!=mp.end()) a[i]=it->second;
else mp[s]=++num,a[i]=num;
}
rts[0]=1,Build();
for(int i=1;i<=n;++i){
rts[i]=++cnt;
Update(a[i],1,n,rts[i-1],rts[i]);
int L=i-k-1,R=i-1;
if(L-1>=1) ans+=Query(a[i],a[i],1,n,rts[R])-Query(a[i],a[i],1,n,rts[L-1]);
else ans+=Query(a[i],a[i],1,n,rts[R]);
}
write(ans);
return 0;
} D.生活在树上( https://ac.nowcoder.com/acm/contest/11223/D )
1.思路：
考虑每个节点只走一步能到达哪些节点——儿子和父亲。如果距离为 2，这条路就到到头了；如果距离为 1，还可以再走一步，到达距离其儿子或父亲为 1 的儿子的儿子、父亲的父亲和父亲的其他儿子。
为了加快速度，我们可以用 be 数组记录一下其儿子中距离自己为 1 的点，这样从每个节点只要扩展一层即可返回。
用链式前向星存儿子 + f 数组存父亲。
时间复杂度 O(n). [大概吧？毕竟刚开始我还以为这是暴力，结果过了...]
2.代码：
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int n,hd[N],be[N],f[N],w[N],tot;
inline int read(){
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=getchar(); }
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
inline void write(int x){
if(x<0){ putchar('-'); x=-x; }
if(x>9) write(x/10);
putchar(x%10+'0');
}
struct Edge{
int to,val,nx;
}e[N];
inline void add(int x,int y,int z){
e[++tot]={y,z,hd[x]},hd[x]=tot;
}
int main(){
n=read();
f[1]=1,w[1]=0;
for(int i=2;i<=n;++i){
f[i]=read(),w[i]=read();
add(f[i],i,w[i]);
if(w[i]==1) ++be[f[i]];
}
for(int i=1;i<=n;++i){
int cnt=1;
for(int j=hd[i];j;j=e[j].nx){
int s=e[j].to,v=e[j].val;
if(v==1) ++cnt,cnt+=be[s];
else if(v==2) ++cnt;
}
if(w[i]==1){
++cnt;
cnt+=be[f[i]]-1;
if(w[f[i]]==1) ++cnt;
}else if(w[i]==2) ++cnt;
write(cnt),putchar('\n');
}
return 0;
} 1.思路：
遇到这种无序的数列先排序。
对于 a[p] ，其如果有一串与之相同的数，不妨将其平移到这串数字最后的位置，胜算更大。
二分查找找到这串相同的数字的最后的数为 a[i]，则 a[i] 一定能打赢 a[1] ~ a[i-1] ，那么对于后面的数，到比赛结束时，它还需要打赢 k - i + 1 场。
显然意见，我们有引理：若 a[i].val < a[j].val，为使 a[i] 这场胜利，必须使用至少一个道具。
那么如果 k - i + 1 > 2，即 i < k - 1，我们至少需要使用三个道具才能打赢 k - i + 1 场，这时直接返回不可能。
否则，如果 k - i + 1 == 2，即 i == k - 1，我们一定要一场一个道具地打赢 2 个人。
其中，a[n] 是一定要打的，因为如果没打 a[n] ，到最后 a[n] 横扫赛场踔厉风发地来找 a[i] 时无道具可用，就必输。
另外一个我们直接挑最弱的 a[i+1] 即可，其他的都交给 a[n] 解决。
这里讨论一下用每个人用哪个道具来对付，即 ( a[i].val >= a[n].val / 2 && a[i].val * 2 >= a[i+1].val ) || (a[i].val * 2 >= a[n].val && a[i].val >= a[i+1].val / 2) 。
最后，如果 k - i + 1 == 1，即 i >= k（因为 i > k 到比赛结束时也一定在后边会有一个胜利者来找它），我们就要分类讨论：
(i).打一场，用两个道具：那必和 a[n] 打，a[i] * 2 V.S a[n] /2 ;
(ii).某个人超越权限用道具和 a[n] 打一场，a[i] 再和这个人打一场，即是否存在这个中间人 a[k]，使得 valid(i,k) 为 1：
这就需要快速在一个 01 串查找是否存在 1 .
我们可以把 0100101... 看成一个多峰函数，1 为峰。
这时我们就可以用多峰函数的三分一定会收敛于一个局部最优解的特性，若存在 1，返回值一定为 1，否则为 0.
时间复杂度 O(nlogn).
2.代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k;
bool ans[N];
struct Node{
int val,num;
bool operator<(const Node &B)const{
return val<B.val;
}
}a[N];
inline int read(){
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=getchar(); }
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
inline void write(int x){
if(x<0){ putchar('-'); x=-x; }
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline bool valid(int i,int j){
return (a[i].val>=a[j].val/2&&a[j].val*2>=a[n].val)||(a[i].val*2>=a[j].val&&a[j].val>=a[n].val/2);
}
bool check(int i){
int l=i+1,r=n-1;
if(l>r) return 0;
while(l<r-1) {
int mid=l+((r-l)>>1),mmid=mid+((r-mid)>>1);
if(valid(i,mid)>valid(i,mmid)) r=mmid;
else l=mid;
}
return valid(i,l)>valid(i,r)?valid(i,l):valid(i,r);
}
int main(){
n=read(),k=read();
for(int i=1;i<=n;++i) a[i].val=read(),a[i].num=i;
sort(a+1,a+n+1);
for(int p=1;p<=n;++p){
int i=upper_bound(a+p,a+n+1,a[p])-a;
if(i==n+1){
ans[a[p].num]=1;
continue;
}
--i;
if(i<k-1) ans[a[p].num]=0;
if(i==k-1) ans[a[p].num]=((a[i].val>=a[n].val/2&&a[i].val*2>=a[i+1].val)||(a[i].val*2>=a[n].val&&a[i].val>=a[i+1].val/2));
if(i>=k) ans[a[p].num]=(a[i].val*2>=a[n].val/2||check(i));
}
for(int i=1;i<=n;++i) write(ans[i]),putchar(' ');
return 0;
} 1.思路：
数形结合的线性规划题，是个细节巨坑的好题。(bushi)
首先我们发现 xy>=k 是个曲线，考虑一下它是不是能去掉。
当然，它是一个比较冗余的条件 —— y 不能等于 1，除非 x = 1，恒有 xy > x + y >=k.
当 x = 1 时，只有 y = k - 1，xy >= k 才不符合要求。
所以我们只考虑 x + y >= k，即 y >= -x +k 这个约束条件即可，到最后特判一下去掉 x = 1、y = k - 1 就行。
那么我们需要画图喽：
(i). n >= k - 1:
方便起见，坐标原点选为 (1,1)，则 y = -x + k 过 (1, k-1) (k-1, 1).
令 S(...) 表示 ... 包括边长在内的整数点(简称整点)的个数，S(x|y) 表示 S(x) - S(y).
如图，S(DAFE | EF) 即为所求.
我们知道 F 为 ( (k-1)/2, (k-1) / 2 )，
S(AB) 这样一条线上的整点数为 k-1，
顶点在原点的等腰直角三角形 S(AOB) = 1 + 2 + ... +k-1 = Sigma(1,k-1)，
正方形 S(DOCE) = n*n，
S(EF) = S(OE) - S(OF) = (n+1) - ((k-1)/2+1) = n - (k-1) / 2，
S(DAFE | EF) = S(ECBF | EF).
则 S(DAFE | EF) = S(DABCE | EF) / 2
= ( S(DOCE) - (S(AOB) - S(AB)) - S(EF) ) / 2
= (n*n - (Sigma(1,k-1) - (k-1)) - (n - (k-1)/2 )) / 2
= (n*n - Sigma(1,k-2) - (n - (k-1)/2 )) / 2.
故此时：
ans+=(n*n-Sigma(1,k-2)-(n-(k-1)/2))/2;
(ii). n < k && n * 2 > k：
同样方便起见，坐标原点换为 O(0,0).
如图，S(EFG | EG) 即为所求（C(n,0), 图中写反了）
我们知道，将 D 点 y = n 带入过 A,B 的直线 y = -x + k，得 P(k-n,0) ，
故 S(FE) = S(EH) = n - (k - n) +1 = n*2 - k + 1，
S(FH) = S(FE) = n*2 - k + 1，
等腰直角三角形 S(FEH) = Sigma(1,n*2 - k + 1).
为使相减时 EG 上的点完整不落地被减掉，我们需要找到 G 左边在 y = x 上的最近的点 T((k-1) / 2, (k-1) / 2)，
故 S(EG) = S(OE) - S(OT) = n - (k - 1) / 2.
故 S(EFG | EG) = S(FEH | EG) / 2
= (Sigma(1,n*2 - k +1) - (n - (k - 1) / 2 )) / 2.
故此时：
ans+=(Sigma(1,n*2-k+1)-(n-(k-1)/2))/2;
(iii). n*2 <= k：压根没有交集，返回 0.
注意，最后可能因为有些情况没要考虑而出现负数，和 0 取个 max 即可。
别忘开 long long .
时间复杂度 O(T) * O(1).
2.代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long
int T;
inline int read(){
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=getchar(); }
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
inline void write(int x){
if(x<0){ putchar('-'); x=-x; }
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline int Sigma(int i,int j){
return i<=j?(i+j)*(j-i+1)/2:0;
}
signed main(){
T=read();
while(T--){
int n=read(),k=read(),ans=0;
if(n>=k-1) ans+=(n*n-Sigma(1,k-2)-(n-(k-1)/2))/2;
else if(n*2>k) ans+=(Sigma(1,n*2-k+1)-(n-(k-1)/2))/2;
if(k-1>=2&&k-1<=n) --ans;
write(max(ans,(int)0)),putchar('\n');
}
return 0;
} 
全部评论
(0) 回帖