牛客想开了大赛2 题解

题目链接:https://ac.nowcoder.com/acm/contest/907#question

A.【六】平面

公式:(n*n+n)/2 + 1,n为直线数目

B.【一】n的约数

枚举质因子和每个质因子的个数，显然个数肯定从多到少。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mx = 1e4 + 10;
int a[100];
ll n,ans;
void dfs(int x,int d,ll ret,ll now){
	ll mi = 1;
	for(int i=1;i<=d;i++){
		mi *= a[x+1]; 
		if(ret>n/mi) break;
		ans = max(ans,now*(i+1));
		dfs(x+1,i,ret*mi,now*(i+1));
	}
}
int main() {
	int t;scanf("%d",&t);
	int tot = 0;
	for(int i=2;i<100;i++){
		bool ok = 0;
		for(int j=2;j<i;j++)
		if(i%j==0) ok = 1;
		if(!ok) a[tot++] = i;
	}
	while(t--){
		scanf("%lld",&n);
		ans = 1;
		dfs(-1,100,1,1);
		printf("%lld\n",ans);
	}
    return 0;
}

C.【快】Rabbit的数列

直接线段树+懒人标记，复杂度感觉是不会超过O(n*log(n))。另外这题数据随机，所以也可以瞎几把搞。

线段树复杂度没有明确证明，口胡吧O(∩_∩)O哈哈~

#include<bits/stdc++.h>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef long long ll;
using namespace std;
const int mx = 1e5 + 10;
int n,m,C;
int x,y,a,b,cnt[mx];
int v[mx<<2],lazy[mx<<2];
void build(int l,int r,int rt)
{
	if(l==r){
		lazy[rt] = 1;
		return ;
	}
	int mid = l+r>>1;
	build(lson);build(rson);
	lazy[rt] = 1;
}
int query(int l,int r,int rt,int c)
{
	int mid = l+r>>1;
	if(c==1){
		if(lazy[rt]){
			if(lazy[rt]==x) return r-l+1;
			return 0;
		}
		return query(lson,c) + query(rson,c);
	}else{
		if(lazy[rt]){
			cnt[lazy[rt]] += r-l+1;
			return 0;
		}
		return query(lson,c) + query(rson,c);
	}
	return 0;
} 
void push_up(int rt){
	if(lazy[rt]){
		lazy[rt<<1] = lazy[rt];
		lazy[rt<<1|1] = lazy[rt];
		lazy[rt] = 0;
	}
}
void update(int l,int r,int rt,int L,int R,int d)
{
	if(L<=l&&r<=R){
		lazy[rt] = d;
		return ;
	}
	push_up(rt);
	int mid = (l+r)>>1;
	if(L<=mid) update(lson,L,R,d);
	if(R>mid) update(rson,L,R,d);
	if(lazy[rt<<1]==lazy[rt<<1|1])
	lazy[rt] = lazy[rt<<1]; 
}
int main() {
	scanf("%d%d%d",&n,&C,&m);
	build(1,n,1);
	while(m--){
		scanf("%d%d%d%d",&x,&y,&a,&b);
		int now = query(1,n,1,1);
		int L = (a+(1ll*now+b)*(1ll*now+b))%n;
		int R = (a+(1ll*now*b%n)*(1ll*now*b%n))%n;
		L++,R++;
		if(L>R) swap(L,R);
		update(1,n,1,L,R,y);
	}
	query(1,n,1,2);
	int ans = 0;
	for(int i=1;i<=C;i++) ans = max(ans,cnt[i]);
	printf("%lld\n",ans);
    return 0;
}

D.【乐】k进制数

由于这个题求的是一个字符串所有的子串有多少数字满足k进制下d(x)=b，这个数字很明显会满足一些性质。考虑这个每次转化的过程，每一次进位相当于把一个k转化成了一个1，也就是说，在数位和mod(k-1)的意义下，转化前和转化后的数字是等价的，最终会成为(x-1)mod(k-1)+1然后就不能动了如果b=0，那么显然只有这个串的所有数字都为0(也就是说这个数字为0)才成立，否则一个串一定不能转化为0否则这个串的和一定在mod(k-1)的意义下和b(mod(k-1))等价，这里简单的前缀和或者维护一个偏置值，维护前面的和(用map啥的)都可以做所以总之按照b=0分类，然后分类计算一下即可。

#include<bits/stdc++.h>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef long long ll;
using namespace std;
const int mx = 1e5 + 10;
int n,m,K,a[mx];
ll pre[mx];
int cnt[mx];
map <int,int> mp;
int main() {
	scanf("%d%d%d",&K,&m,&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		pre[i] = pre[i-1] + a[i];
		cnt[i] = 0;
		if(!a[i]) cnt[i] = cnt[i-1] + 1;
	}
	ll ans = 0;
	mp[0] = 1;
	for(int i=1;i<=n;i++){
		if(m==K-1){
			int c = pre[i]%(K-1);
			ans += mp[c] - cnt[i];
		}else if(m==0){
			ans += cnt[i];
		}else{
			int c = pre[i]%(K-1);
			c = (c-m+(K-1))%(K-1);
			ans += mp[c];
		} 
		if(!mp.count(pre[i]%(K-1))) mp[pre[i]%(K-1)] = 1;
		else mp[pre[i]%(K-1)]++;
	}
	printf("%lld\n",ans);
    return 0;
}

E.【中】假的字符串

首先建一个字典树，然后呢根据大小关系在当前转态下建立某个字符与其他字符的大小关系，然后拓扑排序看下是否有解。

还有注意的是如果该字符串包含了其他的串，那么肯定无解。

#include<bits/stdc++.h>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef long long ll;
using namespace std;
const int mx = 3e4 + 10;
string s[mx];
int n,rt,tot;
int nxt[mx*10][26];
int vis[33],in[33];
bool ok[mx],eng[mx*10];
vector <int> g[33];
void add(int x){
    int now = rt;
    for(int i=0;i<s[x].length();i++){
        int id = s[x][i] - 'a';
        if(!nxt[now][id])
        nxt[now][id] = tot++;
        now = nxt[now][id];
    }
    eng[now] = 1;
}
bool toupu(){
    int siz = 0;
    queue <int> q;
    for(int i=0;i<26;i++){
        if(!in[i]) q.push(i),siz++;
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int v:g[u]){
            in[v]--;
            if(!in[v]) q.push(v),siz++;
        }
    }
    return siz==26;
}
bool check(int x){
    int now = rt,c = 0;
    for(int i=0;i<30;i++) g[i].clear();
    memset(in,0,sizeof(in));
    for(int i=0;i<s[x].length();i++){
        int id = s[x][i] - 'a';
        if(i!=s[x].length()-1&&eng[nxt[now][id]])
        return 0;
        for(int j=0;j<26;j++){
            if(j!=id&&nxt[now][j]){
                g[id].push_back(j);
                in[j]++;
            }
        }
        now = nxt[now][id];
    }
    return toupu();
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    rt = tot++;
    for(int i=0;i<n;i++) cin >> s[i],add(i);
    int ans = 0;
    for(int i=0;i<n;i++){
        if(check(i)){
            ans++;
            ok[i] = 1;
        }
    }
    cout << ans << endl;
    for(int i=0;i<n;i++){
        if(ok[i]) cout << s[i] << endl;
    }
    return 0;
}

F.【奖】出题人的无向图

一个个分开处理肯定是不行的，那么我考虑离线，将查询的vi从小到大排序，相当于越往后就会有新的点被加入进来。

然后就是并查集+启发式合并，小的树合并到大的树上面去，另外k个点随便用set暴力删除然后再暴力插入即可。

#include<bits/stdc++.h>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int mx = 2e5 + 10;
int n,m,K,a[mx],b[mx];
int ret[mx*3],fa[mx],cnt[mx];
multiset <int> st;
vector <int> g[mx];
map <int,int> mp[mx];
int find(int x){
	return x==fa[x]? x:fa[x]=find(fa[x]);
}
struct node{
	int p,v;
	bool operator < (node A)const{return v < A.v;}
}s[mx];
struct edge{
	int v,p;
	vector<int> r;
	bool operator < (edge A)const{return v < A.v;}
}e[mx*3];
void merge(int x,int y){
	x = find(x);
	y = find(y);
	if(x==y) return ;
	st.erase(st.find(cnt[x]));
	st.erase(st.find(cnt[y]));
	if(mp[x].size()<mp[y].size()) swap(x,y);
	fa[y] = x;
	for(auto it:mp[y]){
		if(mp[x][it.fi]&&mp[x][it.fi]%K==0) cnt[x]--;
		mp[x][it.fi] += it.se;
		if(mp[x][it.fi]%K==0) cnt[x]++;
	}
	st.insert(cnt[x]);
}
void add(int p){
	fa[p] = p;
	mp[p][b[p]] = 1;
	if(K==1) cnt[p] = 1;
	st.insert(cnt[p]);
	for(int v:g[p]) if(fa[v]){
		merge(p,v);
	}
}
int solve(int p,int x){
	while(p<=n&&s[p].v<=e[x].v) add(s[p++].p);
	int siz = e[x].r.size();
	set <int> s1;
	for(int i=0;i<siz;i++) if(fa[e[x].r[i]])
	s1.insert(find(e[x].r[i]));
	for(auto it:s1)
	st.erase(st.find(cnt[it]));
	if(st.empty()) ret[e[x].p] = 0;
	else ret[e[x].p] = *st.rbegin();
	for(auto it:s1) st.insert(cnt[it]);
	return p;
}
int main(){
 	scanf("%d%d%d",&n,&m,&K);
 	for(int i=1;i<=n;i++){
 		scanf("%d",a+i);
 		s[i].v = a[i],s[i].p = i; 
	}
	for(int i=1;i<=n;i++) scanf("%d",b+i);
	int u,v,q;
	while(m--){
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d",&e[i].v);
		e[i].p = i;
		scanf("%d",&u);
		for(int j=1;j<=u;j++){
			scanf("%d",&v);
			e[i].r.push_back(v);
		}
	}
	sort(s+1,s+1+n);
	sort(e+1,e+1+q);
	for(int i=1,p=1;i<=q;i++) 
	p = solve(p,i);
	for(int i=1;i<=q;i++) printf("%d\n",ret[i]);
    return 0;
}

牛客想开了大赛2 题解

继续阅读

HDU 3397 Sequence operation

HDU 5685 Problem A

sqli-labs第一关--报错注入练习

python之判断字符里面有没有|8

浅谈MFC CSting类拼接效率

【多项式】拉格朗日插值

C和java中关于字符串与字符数组的定义和转化

Java：String类字符串与数组之间的转换

Java中 byte[] 数组与 String 字符串的转化

回文树学习小结

HDU 5923 Prediction

HDU 5381 The sum of gcd

D. Ehab the Xorcist(构造+思维)

D. Dreamoon and Sets(构造+数论)

POJ 1284 Primitive Roots (欧拉函数&原根定理)

查找文件中的字符串