2019牛客暑期多校训练营（第二场）F,H,A,D,B
程序员文章站
2022-04-02 18:48:07
...
以后每周打牛客重现赛
F. Partition problem
递归组合数枚举。
先把所有人当成红队，再组合数枚举7个人移到白队，每次移动改变的竞争值可以在On的复杂度内算出。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 LL;
//typedef unsigned long long ull;
//#define F first
//#define S second
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
const ld PI=acos(-1);
const ld eps=1e-9;
//unordered_map<int,int>mp;
#define ls (o<<1)
#define rs (o<<1|1)
#define pb push_back
//#define a(i,j) a[(i)*(m+2)+(j)] //m是矩阵的列数
//pop_back()
const int seed=131;
const int M = 1e5+7;
/*
int head[M],cnt;
void init(){cnt=0,memset(head,0,sizeof(head));}
struct EDGE{int to,nxt,val;}ee[M*2];
void add(int x,int y,int z){ee[++cnt].nxt=head[x],ee[cnt].to=y,ee[cnt].val=z,head[x]=cnt;}
*/
int n,N;
int a[30][30];
bool vs[30];
ll ma;
ll ct=0;
void cal(int x,int num,ll ans)//判断第x个人选不选，已经选了num个人到白队，目前分组的竞争力是ans
{
if(num>n||num+(N-x+1)<n)
return ;
if(x==N+1)
{
ma=max(ma,ans);
return ;
}
ll tp=ans;
for(int i=1;i<=N;i++)
{
if(vs[i])//i是白队
ans-=a[x][i];
else ans+=a[x][i];//i是红队
}
vs[x]=true;
cal(x+1,num+1,ans);//选x 到白队
vs[x]=false; //把x从白队退到红队
cal(x+1,num,tp);//留x在红队
}
/*
两种写法 都可
void dfs(int x, int c, ll sum)
{
if(c == n){ //已经选择了n个人到白队
ma = max(ma, sum);
return;
}
for(int i = x + 1; i <= n + c + 1; i ++){ //保证剩下的够选
ll temp = sum;
for(int j = 1; j <= 2 * n; j ++){
if(in[j])
sum -= a[i][j];
else
sum += a[i][j];
}
in[i] = true;
ct++;
dfs(i, c + 1, sum);
in[i] = false; //回溯
sum = temp;
}
}
*/
int main()
{
scanf("%d",&n);
N=n*2;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
scanf("%d",&a[i][j]);
vs[1]=true;//先把1设成白队
ll ans=0;
for(int i=2;i<=N;i++)ans+=a[1][i];
cal(2,1,ans);
printf("%lld\n",ma);
return 0;
}
/*
3
0 25 64 22 33 68
25 0 6 98 26 34
64 6 0 28 72 83
22 98 28 0 51 43
33 26 72 51 0 62
68 34 83 43 62 0
*/H。Second Large Rectangle
每一行跑一遍单调栈，找出以i为底边的四边形，的最大子矩阵，并把记录的矩形 h*w,(w-1)*h，也记录下来。
否则第二大矩形会找不到。因为单调栈执行过程中会把第二大当成不优解给排除，由于高-1在下一行会算到，我们只记录宽-1形成的小矩形即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 LL;
//typedef unsigned long long ull;
//#define F first
//#define S second
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
const ld PI=acos(-1);
const ld eps=1e-9;
//unordered_map<int,int>mp;
#define ls (o<<1)
#define rs (o<<1|1)
#define pb push_back
//#define a(i,j) a[(i)*(m+2)+(j)] //m是矩阵的列数
//pop_back()
const int seed=131;
const int M = 1007;
const int N =1e7;
/*
int head[M],cnt;
void init(){cnt=0,memset(head,0,sizeof(head));}
struct EDGE{int to,nxt,val;}ee[M*2];
void add(int x,int y,int z){ee[++cnt].nxt=head[x],ee[cnt].to=y,ee[cnt].val=z,head[x]=cnt;}
*/
char S[M][M];
int h[M][M];//第i行第j列，向上最多扩展多少。
int s[M],w[M];
int ar[N],sz;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",S[i]+1);
int ct=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(S[i][j]=='1')h[i][j]=h[i-1][j]+1,ct++;
else h[i][j]=0;
}
for(int i=1;i<=n;i++)
{
int p=0,ans=0;
memset(s,0,sizeof(s));
memset(w,0,sizeof(w));
for(int j=1;j<=m+1;j++)
{
if(h[i][j]>s[p])s[++p]=h[i][j],w[p]=1;
else {
int wi=0;
while(s[p]>h[i][j])
{
wi+=w[p];
ar[++sz]=wi*s[p];
if(wi>1)ar[++sz]=(wi-1)*s[p];
ans=max(ans,wi*s[p]);
p--;
}
s[++p]=h[i][j],w[p]=wi+1;
}
}
}
sort(ar+1,ar+1+sz);
if(sz<=1)puts("0");
else printf("%d\n",ar[sz-1]);
return 0;
}
/*
3 7
1010100
1111100
1111111
1 4
1110
*/[A. Eddy Walker]
打表找规律或者推公式：
1：打表
#include <bits/stdc++.h>
using namespace std;
int vs[100],nm[100];
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
srand((unsigned int)(time(NULL)));
int n;
scanf("%d",&n);
for(int i=1;i<=100000;i++)
{
int now=rand()%2;
memset(vs,0,sizeof(vs));
int tp=0,ct=1;
vs[0]=1;
while(ct<n)
{
now=rand()%2;
if(now)tp=(tp+1)%n;
else tp=(tp+n-1)%n;
if(!vs[tp])ct++,vs[tp]=1;
}
nm[tp]++;
}
for(int i=0;i<n;i++)
printf("%d ",nm[i]);
return 0;
}发现规律：到每个点的概率都相同，到0点概率为0
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
ll ans=1;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d %d",&n,&m);
ll tp;
if(m==0)tp=0;else tp=n-1;
if(n==1)tp=1;
ans=(ans*tp)%mod;
printf("%lld\n",ans);
}
return 0;
}AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1000000007;
ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)ans=a*ans%mod;
a=a*a%mod;
b/=2;
}
return ans%mod;
}
int main()
{
int t;
ll ans=1;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d %d",&n,&m);
ll tp;
if(m==0)tp=0;else tp=n-1;
if(n==1)tp=1;
ans=(ans*qpow(tp,mod-2))%mod;
printf("%lld\n",ans);
}
return 0;
}
推公式：
假设答案是：f(n,m)。
1：首先f(n,0)=0.(n>1)，走完其他点就直接停了
2：然后 f(n,i)=f(n,n-i+1). 因为左右走概率相同，最后停在前面一个的概率，肯定等于停在后面一个的概率（注意它是个环）。
3：最后，f(n,i)=f(n,(i+n-1)%n)+f(n,(i+1)%n)/2，即停在一个点的概率等于停在其前面一个点的概率+后面一个点的概率除以二。
因为：
最后停在点i。上一步必定是在i+1,或者i-1.
假设上一步是i+1，如果走完除了i点以外的所有点，且最后一步是i+1的概率是x1。那么在这x1概率中，有1/2的概率走向i点，1/2的概率到i+2（不会再回到i+1点，最后一步到i+1所有的概率已经是x了）所以最后一步停在i 点的概率：p+=1/2*x。
同理 p+=1/2*x2（最后一步停在i-1，且已经走完除了i的所有点的概率）
所以3结论成立。
由2、3可推出f(n,i) 任取 (1<i<n)都相同。（可以自己尝试推下，比较简单，或者直接画图就出来了）
所以得出：
f(1,0)=1;
f(n,m)=1/n;
f(n,0)=0;
D:Kth Minimum Clique
最大集团数2^100.
直接求第k小不好求，枚举出集团数会T。
求第K小，一般可以看看能不能从第一小开始递推。
我们发现：最小的是空集。
然后往空集这个集团加一个点。
得到的集团中选个最小的（此时的集团一定是第二小）再往这个集团加一个可行点。
然后再取最小的集团（此时的集团一定是第三小）。
当前最小权值集团，一定是第i小，i为执行次数+1.
新的集团一定要通过当前集团一个新的点得到。而点的权值为正数。所以当前最小一定是第i小。
1.取最小集团这个操作明显可以用优先队列来做。
2.而判断一个点能否可以加入一个集团里，为了On的判断出来，我们可以用bitset进行维护。
bitset中1代表集团中包含的点。判断某点能否加入集团中，只需判断，这个集团的点是否都在这个点能连的点中。
所以读入连边时直接用bitset维护即可。
3.为了防止重复我们可以记录每个集团点编号最大的，加点时只能选择id更大的点加入，刚好是组合型枚举
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll w[110];
struct node{
ll val;
int lst;
bitset<101>s;
bool operator <(const node &r)const{
return val>r.val;
}
};
priority_queue<node>q;
bitset<101>e[101];
char S[101];
int main()
{
//freopen("3.in","r",stdin);
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
for(int i=1;i<=n;i++){
scanf("%s",S+1);
for(int j=1;j<=n;j++)
if(S[j]=='1')e[i][j]=1;else e[i][j]=0;
}
if(k==1){
printf("0\n");return 0;
}
bitset<101>p;
q.push(node{0,0,p});
int nm=0,ct=0;
//由于优先队列里都是正数，
//任意数再加上一个正数必然大于当前存的权值最小的集团的权值
//。所以堆头一定是当前最小权值集团
while(!q.empty())
{
node tp=q.top();q.pop();
nm++;
if(nm==k)
{
printf("%lld\n",tp.val);
return 0;
}
bool f=false;
for(int i=tp.lst+1;i<=n;i++)//从当前点后面的点进行选择，去重
{
bitset<101>now(tp.s);
if((e[i]&now)==now)//这个点可以加入tp这个小集团里
{
now[i]=1;
q.push(node{tp.val+w[i],i,now});
}
}
}
printf("-1\n");
return 0;
}
/*
5 13
545656160 714825755 534642371 950076512 270441846
00111
00110
11011
11101
10110
1484718883
*/B.Eddy Walker 2
https://blog.csdn.net/yiqzq/article/details/96635574
学习这个大佬的思路
https://www.cnblogs.com/Yinku/p/11220848.html
抄了这个大佬的BM板子
这题就结束了。。。。瑟瑟发抖
思路蛮简单的，主要是k=-1时不好做。
https://www.zhihu.com/question/336062847?utm_source=qq&utm_medium=social&utm_oi=1017107436351676416
自行移步知乎进行学习。。考场上还是靠直觉或者打表吧。
下面说下我的比较通俗的理解
在足够长时间之后，平均每次前进k+1/2步，因此平均停留次数就是2/(k+1);
或者更简单的说，无穷大后，每(k+1)/2个点会到达一次。即最后到达的点是 ：(k+1)/2，(k+1)/2 *2，(k+1)/2*3……
而无穷大的终点落在在某个我们达到点的概率是1/[(k+1)/2]=2/(k+1);(相当于终点不固定随机定)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head
ll n,k;
namespace linear_seq {
const int N=10010;
ll res[N],base[N],_c[N],_md[N];
vector<int> Md;
void mul(ll *a,ll *b,int k) {
rep(i,0,k+k) _c[i]=0;
rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
for (int i=k+k-1;i>=k;i--) if (_c[i])
rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
rep(i,0,k) a[i]=_c[i];
}
int solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
ll ans=0,pnt=0;
int k=SZ(a);
assert(SZ(a)==SZ(b));
rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
Md.clear();
rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
rep(i,0,k) res[i]=base[i]=0;
res[0]=1;
while ((1ll<<pnt)<=n) pnt++;
for (int p=pnt;p>=0;p--) {
mul(res,res,k);
if ((n>>p)&1) {
for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
}
}
rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
if (ans<0) ans+=mod;
return ans;
}
VI BM(VI s) {
VI C(1,1),B(1,1);
int L=0,m=1,b=1;
rep(n,0,SZ(s)) {
ll d=0;
rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
if (d==0) ++m;
else if (2*L<=n) {
VI T=C;
ll c=mod-d*powmod(b,mod-2)%mod;
while (SZ(C)<SZ(B)+m) C.pb(0);
rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
L=n+1-L; B=T; b=d; m=1;
} else {
ll c=mod-d*powmod(b,mod-2)%mod;
while (SZ(C)<SZ(B)+m) C.pb(0);
rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
++m;
}
}
return C;
}
int gao(VI a,ll n) {
VI c=BM(a);
c.erase(c.begin());
rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
}
};
ll f[3000];
int main() {
vector<int>v;
int nCase;
scanf("%d", &nCase);
while(nCase--){
scanf("%lld%lld",&k, &n);
memset(f,0,sizeof(f));
v.clear();
f[1]=1;v.push_back(f[1]);
for(int i=2;i<=k*2;i++)
{
for(int j=max(1ll,i-k);j<i;j++)
f[i]=(f[i]+f[j])%mod;
f[i]=f[i]*powmod(k,mod-2)%mod;
v.push_back(f[i]);
// cout<<f[i]<<" "<<i<<" "<<k<<" "<<powmod(k,mod-2)<<endl;
}
if(n==-1)
printf("%lld\n",2*powmod(k+1,mod-2)%mod);
else
printf("%lld\n",1LL * linear_seq::gao(v,n) % mod);
}
}
推荐阅读
-
2019牛客暑期多校训练营（第二场）H Second Large Rectangle
-
2020牛客暑期多校 第二场 B Boundary（计算几何）
-
2020牛客暑期多校训练营（第二场）B.Boundary(计算几何)
-
2019牛客暑期多校训练营（第一场） B Integration （公式推导）
-
2019牛客暑期多校训练营（第二场）H Second Large Rectangle
-
2020牛客暑期多校训练营（第二场）——B
-
2020牛客暑期多校训练营（第二场）B-Boundary
-
2020牛客暑期多校训练营（第二场）F
-
2020牛客暑期多校训练营（第二场）B.Boundary
-
2020牛客暑期多校训练营（第二场）——H