文章目录
“卓见杯”第五届CCPC中国大学生程序设计竞赛河南省赛
题解终于写完了，哈哈哈哈哈哈哈！2019/4/17
A 最大下降矩阵
最长下降子序列，简单dp题，第一开始数据错了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
// A
const int maxn =300+10;
int dp[maxn];
LL ar[maxn][maxn];
int n,m;
bool check(int x,int y){
for(int i = 1;i <= m; ++i)
if(ar[x][i] <= ar[y][i])
return false;
return true;
}
int main()
{
cin>>n>>m;
for(int i = 1;i <= n; ++i){
for(int j = 1;j <= m; ++j)
scanf("%lld",&ar[i][j]);
}
for(int i= 1;i <= n; ++i)
dp[i] = 1;
int ans = 0;
for(int i = 1;i <= n; ++i){
for(int j = i+1;j <= n; ++j)
if(check(i,j))
dp[j] = max(dp[j],dp[i]+1);
ans = max(ans,dp[i]);
}
cout<<n-ans<<endl;
return 0;
}
B 树上逆序对
先学知识：
主席树：可持续化线段树
树上主席树：在数组上有i-1 推出i的线段树，同样，由父节点推出根节点的线段树，需要树上主席树，这样就可以直接查询从根到某个节点比这个节点值大的有多少个
dfs序，通过dfs序将树形结构转化成线性结构，然后就可以利用dfs序建立树状数组，树状数组用来求和，比如某个子树在dfs序上从 i到j，那么求和就可以用sum(j)-sum(i-1)
我们用主席树统计每一个节点的贡献，然后用树状数组进行单点修改，区间求和，求出子树的贡献，用总的减去就可得答案
细节：需要先将所有询问加入的节点的值也加入到离散化中去
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;
const int maxn = 2e5+10;
// 主席树
int sum[maxn*20],Left[maxn*20],Right[maxn*20],tot,root[maxn];
int Build(int l,int r){
int rt = (++tot);
if(l == r) return rt;
int m = (l+r)>>1;
Left[rt] = Build(l,m);
Right[rt] = Build(m+1,r);
return rt;
}
int Update(int pre,int l,int r,int x,int p){
int rt = ++tot;
Left[rt] = Left[pre],Right[rt] = Right[pre],sum[rt] = sum[pre]+p;
if(l < r){
int m = (l+r)>>1;
if(x <= m)
Left[rt] = Update(Left[pre],l,m,x,p);
else
Right[rt] = Update(Right[pre],m+1,r,x,p);
}
return rt;
}
int Query(int u,int l,int r,int L,int R){
if(L <= l && R >= r) return sum[u];
int m = (l+r)>>1;
LL ans = 0;
if(L <= m)
ans += Query(Left[u],l,m,L,R);
if(R > m)
ans += Query(Right[u],m+1,r,L,R);
return ans;
}
int a[maxn],Hash[maxn],nn;
bool Addnode[maxn];
vector<int> G[maxn];
int op[maxn],U[maxn],X[maxn];// 用于保存询问
// 树状数组
LL tree[maxn];
void Add(int x,int p){
while(x < maxn)
tree[x] += p,x += lowbit(x);
}
LL Sum(int x){
LL s = 0;
while(x > 0)
s += tree[x],x -= lowbit(x);
return s;
}
int Dfs[maxn],nxt[maxn];
int dfs_clock;
void dfs(int node,int fa){
Dfs[node] = ++dfs_clock;
if(!Addnode[node]){
Add(Dfs[node],Query(root[fa],1,nn,a[node]+1,nn));
root[node] = Update(root[fa],1,nn,a[node],1);
}
for(auto c: G[node])
dfs(c,node);
nxt[node] = dfs_clock;
}
int main(void){
int n,m;
cin>>n>>m;
for(int i = 1;i <= n; ++i)
scanf("%d",&a[i]);
for(int i = 2;i <= n; ++i){
int t;scanf("%d",&t);
G[t].push_back(i);
}
for(int i = 1;i <= m; ++i){
scanf("%d%d",&op[i],&U[i]);
if(op[i] == 1){
scanf("%d",&X[i]);
a[++n] = X[i];
X[i] = n;
G[U[i]].push_back(n);
Addnode[n] = true;
}
}
for(int i = 1;i <= n; ++i)
Hash[i] = a[i];
Hash[++n] = 1e9+2;
sort(Hash+1,Hash+n+1);
nn = unique(Hash+1,Hash+n+1)-(Hash+1);
for(int i = 1;i <= n; ++i)
a[i] = lower_bound(Hash+1,Hash+nn+1,a[i])-Hash;
root[0] = Build(1,nn);
dfs(1,0);
// cout<<Query(1,1,nn,2,nn)<<endl;
for(int i = 1;i <= m; ++i){
if(op[i] == 1){
Add(Dfs[X[i]],Query(root[U[i]],1,nn,a[X[i]]+1,nn));
// cout<<U[i]<<endl;
// cout<<a[X[i]]+1<<endl;
// cout<<Query(U[i],1,nn,a[X[i]]+1,nn)<<endl;;
root[X[i]] = Update(root[U[i]],1,nn,a[X[i]],1);
}
else{
// cout<<Sum(n)<<" "<<Sum(nxt[U[i]])<<endl;
printf("%lld\n",Sum(n)-Sum(nxt[U[i]])+Sum(Dfs[U[i]]-1));
}
}
return 0;
}
C 大小接近的点对
进入子树之前算一下有多少个满足条件，离开之前之后算一下，二者做差即为这个节点的贡献，好简单啊，zdwtxdy!!!
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
typedef long long LL;
int n,k,tot;
int tree[maxn],a[maxn],b[maxn];
// int Hash(int x){
// return lower_bound()
// }
void Add(int x,int p){
while(x < maxn)
tree[x] += p,x += x&(-x);
}
int Sum(int x){
LL s = 0;
while(x > 0)
s += tree[x],x-= x&(-x);
return s;
}
vector<int> G[maxn];
LL ans[maxn];
void dfs(int node){
ans[node] = 1;
int l = lower_bound(b+1,b+tot+1,a[node]-k)-b;
int r = upper_bound(b+1,b+tot+1,a[node]+k)-b-1;
// cout<<a[node]<<" "<<l<<" "<<r<<endl;
LL pre = Sum(r)-Sum(l-1);
for(auto c: G[node]){
dfs(c);
ans[node] += ans[c];
}
LL nxt = Sum(r)-Sum(l-1);
// cout<<nxt<<endl;
ans[node] += nxt-pre;
int t = lower_bound(b+1,b+tot+1,a[node])-b;
// cout<<t<<endl;
Add(t,1);
}
int main(void){
cin>>n>>k;
for(int i = 1;i <= n; ++i)
scanf("%d",&a[i]),b[i] = a[i];
sort(b+1,b+n+1);
tot = unique(b+1,b+n+1)-(b+1);
// cout<<tot<<endl;
for(int i = 2;i <= n; ++i){
int u;scanf("%d",&u);
G[u].push_back(i);
}
// cout<<G[1].size()<<endl;
dfs(1);
// cout<<Sum(4)<<endl;
for(int i = 1;i <= n; ++i)
printf("%lld\n",ans[i]);
return 0;
}
D 文本修正
import java.math.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
s=s.replaceAll("\\bhenan\\b", "Henan");
System.out.println(s);
}
}
F 咕咕的计数题 II
当 n/a>=n/a+1就存在，然后找规律发现大于 a∗(a+1) 时，肯定满足，然后小于 a(a+1) 就是 a 个 a+1 的循环节，循环节中满足条件的个数递增
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
ll a;
inline ll read()
{
ll x = 0, w = 0; char ch = getchar();
while (!isdigit(ch))
{
w != ch == '-'; ch = getchar();
}
while (isdigit(ch))
{
x = (x << 3) + (x <<1) + (ch ^ 48); ch = getchar();
}
return w? -x: x;
}
ll solve(ll n)
{
if (n < a) return 0;
if (n == a) return 1;
ll ans = 0;
LL nn = n-a;
//n a*(a+a) n - a
nn = sqrt((double)n+0.5);
if (nn >= a)
{
ans += n - a * (a + 1) + 1;
n = a * (a + 1)-1;
}
ll nloop = n / (a + 1), nleft = n % (a + 1);
ans += (1 + nloop)* nloop/2;
if(nleft == 0) return ans;
nloop++;
ans += max(nleft-(a+1-nloop) + 1,0LL);
return ans;
}
int main()
{
//ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin>>T;
while (T--)
{
a = read();
ll l, r;
l = read(),r = read();
printf("%lld\n",solve(r) - solve(l - 1));
//cout<< solve(r) - solve(l - 1) <<"\n";
}
return 0;
}
E咕咕的的复复读读机机
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
//
inline int read()
{
int x = 0, w = 0; char ch = getchar();
while (!isdigit(ch))
{
w != ch == '-'; ch = getchar();
}
while (isdigit(ch))
{
x = (x << 3) + (x <<1) + (ch ^ 48); ch = getchar();
}
return w? -x: x;
}
const int MAXN = 100 + 5;
int a[MAXN];
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; n =read();
for (int i = 0; i <n; i++)
{
int x = read();
a[x]++;
}
int ans = 0, id = 0;
for (int i = 0; i <=100; i++)
{
if (a[i] > ans)
{
id = i;
ans = a[i];
}
}
cout<<id<<endl;
return 0;
}
G 咕咕的 01 图
题解少了一个"/" 号，看了半天没看懂
简而言之，我们按照边权讨论，每一个节点如果对于一个边权是奇数度节点，那么他就对答案有贡献，贡献是1/2 因为一条链两头奇数度节点，有贡献一条边
考虑边权全部为 1 的情况，事实上就是奇数度数结点的个数/2，那么考虑按照边权相同去处
理所有边即可。有个更直观的想法，同样是边权相同的一并处理，那么把o看成点，--看
成是边，那么o--o--o--o--o本身可以断裂为o-,-o-,-o-,-o-,-o，在这之中只有-o-是不会对答案有贡献的
#include <bits/stdc++.h>
using namespace std;
char buf[1<<20];
int ed,pt;
const int maxn = 1e6+19;
int a[maxn],b[maxn],w[maxn];
int cnt[maxn];
bool vis[maxn];
vector<int> son[maxn];
vector<int> line;
int main(void){
int T;scanf("%d",&T);
while(T--){
int n,m;scanf("%d%d",&n,&m);
for(int i = 0;i < m; ++i)
scanf("%d%d%d",&a[i],&b[i],&w[i]);
for(int i = 0;i < m; ++i)
line.push_back(w[i]),vis[w[i]] = true;
for(int i = 0;i < m; ++i)
son[w[i]].push_back(a[i]),son[w[i]].push_back(b[i]);
long long ans = 0;
int tmp = 0;
for(auto aw:line){
if(!vis[aw]) continue;
vis[aw] = false;
tmp = 0;
for(auto x:son[aw])
cnt[x]++;
for(auto x:son[aw]){
if(cnt[x]&1)
tmp++;
cnt[x] = 0;
}
ans += (1ll*tmp*aw/2);
}
for(auto aw: line)
son[aw].clear();
line.clear();
printf("%lld\n",ans);
}
return 0;
}
H 咕咕的搜索序列
dfs求出原树的合法序列，然后比对，关键在于选择哪一个子节点进行遍历，第一开始考虑到直接按照他们在给定序列中出现的顺序排序（我记得是cf原题），wa掉了，然后考虑到有些没有，就先dfs求出整个子树里面节点的出现顺序最早的，然后再排序，过掉了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int maxn = 1e6+10;
vector<int> G[maxn];
int nxt[maxn],a[maxn];
int c[maxn];
int n,m;
int cnt = 0;
int M[maxn];
void dfs1(int node){
if(c[node]!= 0)
M[node] = min(M[node],c[node]);
for(auto c: G[node]){
dfs1(c);
M[node] = min(M[node],M[c]);
}
}
void dfs(int node){
for(auto c:G[node]){
dfs(c);
}
nxt[++cnt] = node;
}
bool cmp(int a,int b){
return M[a] < M[b];
}
int main()
{
int T;cin>>T;
while(T--){
scanf("%d%d",&n,&m);
cnt = 0;
for(int i = 1;i <= n; ++i)
G[i].clear(),a[i] = nxt[i]= c[i] = 0,M[i] = 1e8;
for(int i = 2;i <= n; ++i){
int aa;scanf("%d",&aa);
G[aa].push_back(i);
}
for(int i = 1;i <= m; ++i)
scanf("%d",&a[i]),c[a[i]]=i;
dfs1(1);
for(int i = 1;i <= n; ++i)
sort(G[i].begin(),G[i].end(),cmp);
dfs(1);
int j = 1;
for(int i = 1;i <= m; ++i){
while(j <= n&&nxt[j] != a[i])
++j;
}
if(j >= n+1)
puts("BAD GUGU");
else
puts("NOT BAD");
}
return 0;
}
I Childhood dream
直接暴力搜索，然后 加两个剪枝就行了，被带偏榜了
剪枝见check
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int maxn = 100+10;
bool use[maxn];
int n,m;
char ar[maxn][maxn];
int x[maxn],y[maxn];
bool have[maxn][maxn];
int ans[maxn];
bool check(int now){
for(int i = 1;i <= n; ++i){
int a1,a2;a1 = a2 = 0;
for(int j = 1;j <= now; ++j){
if(ans[j] == ar[i][j]){
a1++;
continue;
}
if(have[i][ans[j]])
a2++;
// if(have[i][ans[j]]&&ans[j] == 8){
//// a2++;
//
// cout<<"8 ="<<ans[1]<<" "<<ans[2]<<" "<<have[i][ans[j]]<<endl;
// }
}
// cout<<ans[now]<<" "<<a1<<" "<<a2<<endl;
if(a1 > x[i] || a2 > y[i]) return false;
if(a1+m-now < x[i] || a2+m-now < y[i]) return false;
}
return true;
}
void dfs(int x){
// cout<<x<<endl;
if(x == m+1){
// cout<<x<<endl;
for(int i = 1;i <= m; ++i)
cout<<ans[i];
cout<<endl;
exit(0);
}
for(int i = 0;i <= 9; ++i){
// cout<<i<<endl;
if(!use[i]){
use[i] = true;
ans[x] = i;
// for(int j = 1;j)
if(!check(x))
{
use[i] = false;
continue;
}
dfs(x+1);
use[i] = false;
}
}
}
int main()
{
// ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i = 1;i <= n; ++i){
cin>>(ar[i]+1)>>x[i]>>y[i];
// cout<<(ar[i]+1)<<endl;
for(int j = 1;j <= m; ++j)
{
ar[i][j] -= '0';
// cout<<(int)ar[i][j]<<endl;
have[i][(int)ar[i][j]] = true;
}
}
dfs(1);
return 0;
}
J THE END IS COMING!!!
瞎了眼没看清样例，我怕不是个傻叉。。。。
转自题解，然后自己码了码代码
思路还是挺巧妙的，首先我们需要知道这k个名额只能用于不能到达的，日狗这点真的坑
第二，我们还要知道元素可以拆分，分成每一个元素分开计算
第三，我们还要知道怎么建图
我们只有 5 种元素，所以可以全部分开考虑
每种元素单独考虑
每个点拆成两部分，一个用于接受元素，一个用于往外送元素。
源点向每个点的接受元素部分建立流量为当前节点需要元素数量，费用为 1 的边。
向用于外送元素的部分建立流量为当前节点需要元素数量，费用为 0 的边。
外送元素部分向所有能及时赶到的部分建立流量为正无穷，费用为 0 的边，意味着同一个元
素又去了其他地方。
每个接受元素的部分向超级汇点建立流量为当前节点需要元素数量，费用为 0 的边，意味着
这个点接收到了足够多的元素。
每个离起点距离不支持的点记录数量，超过 k 就是无解。
处理过程中跳过这些点就好了
总结一下就是
对于每一个点从源点到这个点建立容量为需求，费用为1的边，从这个点到终点建立容量为需求，费用为0的边
对于可能发生的转移，我们需要一个虚拟节点，代表的是i这个节点能向其它转移的元素的个数，所以从源点开始向虚拟节点连接容量为需求，费用为0的点，同时向所有能转移的点连接容量为需求，费用为0的节点
这样子为什么是正确的呢？
我想了想，对于每一个节点，可以从源点直接拿元素，也可以由其他转移过来，但是最大流是固定的，就是所有的需求，所以即使求最小费用的过程，当你不能从其它节点得到流量，只能通过自己从源点拿元素，费用为1，以保证最大流
#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define For(i,a,b) for(int i = a; i < b; ++i)
#define IOS ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int prime = 999983;
const int INF = 1e8;
const LL INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
struct Edge{
int from,to,cap,flow,cost;
};
const int maxn = 5000+100;
struct MCMF{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
int inq[maxn];
int d[maxn];
int p[maxn];
int a[maxn];
void init(int n){
this->n = n;
for(int i = 0;i < n; ++i) G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int cap,int cost){
edges.push_back((Edge){from,to,cap,0,cost});
edges.push_back((Edge){to,from,0,0,-cost});
int m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BellmanFord(int s,int t,int &flow,int &cost){
for(int i = 0;i < n; ++i) d[i] = INF;
memset(inq,0,sizeof(inq));
d[s] = 0,inq[s] = 1;p[s] = 0,a[s] = INF;
queue<int> Q;
Q.push(s);
while(!Q.empty()){
int u = Q.front(); Q.pop();
inq[u] = 0;
for(int i = 0;i < G[u].size(); ++i){
Edge& e = edges[G[u][i]];
if(e.cap > e.flow &&d[e.to] > d[u]+e.cost){
d[e.to] = d[u]+e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u],e.cap-e.flow);
if(!inq[e.to]) {
Q.push(e.to); inq[e.to] = 1;
}
}
}
}
if(d[t] == INF) return false;
flow += a[t];
cost += d[t]*a[t];
int u = t;
while(u != s){
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];
u = edges[p[u]].from;
}
return true;
}
int Mincost(int s,int t,int &flow,int &cost){
flow = 0,cost = 0;
while(BellmanFord(s,t,flow,cost));
return cost;
}
};
MCMF mcmf;
// const int maxn = 100+10;
int x[maxn],y[maxn],st[maxn],ut[maxn],c[maxn][6];
int sx,sy;
bool keda[maxn];
int main(void)
{
int n,m,k;
cin>>n>>m>>k;
cin>>sx>>sy;
int cnt = 0;
for(int i = 1;i < n; ++i){
cin>>x[i]>>y[i]>>st[i]>>ut[i];
for(int j = 1;j <= m; ++j)
cin>>c[i][j];
int dis =abs(x[i]-sx)+abs(y[i]-sy);
if(dis > st[i])
cnt++;
else
keda[i] = true;
}
if(cnt > k)
return 0*puts("THE END IS COMING!!!!!");
// cout<<cnt<<endl;
int ans = 0;
for(int j = 1;j <= m; ++j){
mcmf.init(2*n+1);
for(int i = 1;i < n; ++i){
if(!keda[i]) continue;
mcmf.AddEdge(0,i,c[i][j],1);
mcmf.AddEdge(i,n+i,c[i][j],0);
mcmf.AddEdge(0,n+i,c[i][j],0);
for(int k = 1;k < n; ++k){
int dis =abs(x[i]-x[k])+abs(y[i]-y[k]);
if(keda[k]&&k != i&&st[i]+ut[i]+dis <= st[k])
{
mcmf.AddEdge(n+i,k,c[i][j],0);
// cout<<i<<" "<<k<<endl;
}
}
mcmf.AddEdge(i,2*n,c[i][j],0);
}
int flow,cost;
ans += mcmf.Mincost(0,2*n,flow,cost);
// ans += cost;
}
cout<<ans<<endl;
// int n,m,s,t;
// scanf("%d %d %d %d",&n,&m,&s,&t);
// int u,v,w,c;
// mcmf.init(n+1);
// while(m--){
// scanf("%d %d %d %d",&u,&v,&w,&c);
// mcmf.AddEdge(u,v,w,c);
// }
// int flow,cost;
// flow = 0,cost = 0;
// mcmf.Mincost(s,t,flow,cost);
// printf("%d %d\n",flow,cost);
return 0;
}
京公网安备 11010502036488号