题目链接: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;
}标签：rt,lazy,return,int,题解,牛客,lson,query,想开 From： https://blog.51cto.com/u_12468613/6384504