A、试题类型：
基本算法。
B、算法模型：
贪心。
C、试题说明：
贪心算法，每次区间越长越好。
枚举深度，用并查集和数组，维护连通性，记录一共被断为几个区间。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100000+50;
int n,a[N],cnt=1,vis[N],maxd; long long ans=0;
int num,last[N],nxt[N],pos[N];
inline void add(int x,int y)
{
nxt[++num]=last[x];
last[x]=num; pos[num]=y;
}
inline void hehe(int x)
{
vis[x]=1;
if(x==1)
{
if(vis[x+1]==1)
{
cnt--; return;
}
else
return;
}
if(x==n)
{
if(vis[x-1]==1)
{
cnt--;
return;
}
else
return;
}
if(vis[x-1]==0 && vis[x+1]==0)
{
cnt++; return;
}
if(vis[x-1]+vis[x+1]==1)
{
return;
}
if(vis[x-1]==1 && vis[x+1]==1)
{
cnt--; return;
}
}
int main()
{/*
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);*/
scanf("%d",&n);
for(int i=0;i<=N-20;i++)
last[i]=-1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
add(a[i],i);
maxd=max(maxd,a[i]);
}
if(n==1)
{
printf("%d",a[1]);
return 0;
}
for(int i=last[0];i!=-1;i=nxt[i])
{
int x=pos[i];
hehe(x);
}
for(int k=1;k<=maxd;k++)
{
ans=1ll*(ans+cnt);
for(int i=last[k];i!=-1;i=nxt[i])
{
hehe(pos[i]);
}
}
printf("%lld\n",ans);
return 0;
}
A、试题类型：
逻辑推理。
B、算法模型：
背包。
C、试题说明：
完全背包问题：
输入每种面额后，先将其从小到大排序。
引理：如果一个面额无法被比它小的面额凑出来，那么必须选，否则一定不选。
证明：前者很显然，因为这个数不可能被比其更大的数凑出来。
后者，因为这个数可以被其它数凑出来，那么需要这个数组成的数只需要凑成这个数的数就可以。
如果发现没被前面的数背包得到就选，否则不选。
#include<bits/locale_facets.h>
#include<memory.h>
#include<stdio.h>
using namespace std;
inline void output(long long value);
inline long long input();
short a[101],able[25001];
int main()
{
short T=input();
while(T--)
{
short n=input(),maximum=0;
short must=n;
for(short i=1;i<=n;i++)
maximum=max(maximum,a[i]=input());
able[0]=true;
for(short i=1;i<=n;i++)
for(short j=a[i];j<=maximum;j++)
if(able[j-a[i]])
able[j]++;
for(short i=1;i<=n;i++)
if(able[a[i]]>1)
must--;
memset(able,0,50002);
output(must),putchar('\n');
}
return 0;
}
inline void output(long long o)
{
if(o<0)
putchar('-'),o=-o;
if(o>=10)
output(o/10);
putchar(o%10^'0');
}
inline long long input()
{
bool positive=true;
char now=getchar();
long long i=0;
for(;!isdigit(now);now=getchar())
if(now=='-')
positive=!positive;
for(;isdigit(now);now=getchar())
i=(i<<3)+(i<<1)+(now^'0');
return positive?i:-i;
}
A、试题类型：
STL问题。
B、算法模型：
multiset、二分。
C、试题说明：
multiset存储，贪心思路：将尽可能多的路径组合起来，然后使剩下的路径中最大的路径尽可能大。组合完之后，将剩下的最大的路径丢给父亲即可。
因为需要剩下的路径尽可能大，所以从小的开始。每次取出最小的，然后找到一个能和它组合起来大于等于mid的尽可能短的路径，然后组合起来，如果找不到，就弃掉这条最小的路径。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define maxn 100010
int n,m;
struct node
{
int x,y,z,next;
};
node e[2*maxn];
int first[maxn];
void buildroad(int x,int y,int z)
{
static int len=0;
e[++len]=(node){x,y,z,first[x]};
first[x]=len;
}
int S,sum;
int dfs(int x,int fa)
{
multiset<int>s;//记录儿子传上来的路径
for(int i=first[x];i;i=e[i].next)
{
int y=e[i].y;
if(y==fa)
continue;
int p=dfs(y,x)+e[i].z;
if(p>=S)
sum++;//假如儿子给的这条路径直接大于S，那么sum+1即可
else
s.insert(p);//否则加入到s里面
}
multiset<int>re;//记录被丢掉的路径
while(s.size()>=2)
{
multiset<int>::iterator mi=s.begin();//找到最小的
int t=*mi;//记录下它的值
s.erase(mi);//无论这个最小的路径能否组合成功它都是要被丢出s的
multiset<int>::iterator pa=s.lower_bound(S-t);//找到一个尽可能小的能和t组合的
if(pa!=s.end())
s.erase(pa),sum++;//假如找得到，那么就配对，把pa从s中删掉，sum+1
else
re.insert(t);//否则把t加入到re里面，表示它被丢掉了，没有用到
}
int ret=0;
if(s.size()>0)
ret=max(ret,*(--s.end()));//找到s里面剩下的 的最大值
if(re.size()>0)
ret=max(ret,*(--re.end()));//找到re里面的最大值
return ret;
}
bool check(int x)
{
S=x;sum=0;
dfs(1,0);
return sum>=m;
}
int main()
{
scanf("%d %d",&n,&m);
int l=1,r=0;
for(int i=1,x,y,z;i<n;i++)
{
scanf("%d %d %d",&x,&y,&z);r+=z;
buildroad(x,y,z);
buildroad(y,x,z);
}
int ans;
while(l<=r)
{
int mid=l+r>>1;
if(check(mid))
ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d",ans);
}
A、试题类型：
路径问题。
B、算法模型：
dfs与hmm。
C、试题说明：
及格分：dfs遍历一遍，优先考虑编号较小的点。
满分：hmm，其实n^2暴力断边就可以了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define FOR(i,n,m) for(register int i=n;i<=m;++i)
using namespace std;
const int N=5010,INF=0x7fffffff;
int n,m,tot,t;
int ans[N][2];
bool g[N][N],vis[N],flag;
int x[N],y[N];
inline int read()
{
int x=0; char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x;
}
void dfs_1(int u)
{
ans[++tot][0]=u; vis[u]=1;
FOR(i,1,n) if(g[u][i]&&!vis[i]) dfs_1(i);
}
bool dfs_2(int u)
{
if((u>ans[tot+1][1])&&(!flag))
return 0;
if(u<ans[tot+1][1])
flag=1;
ans[++tot][0]=u; vis[u]=1;
FOR(i,1,n) if(g[u][i]&&!vis[i])
if(!dfs_2(i))
return 0;
return 1;
}
int main()
{
n=read(); m=read();
FOR(i,1,n) ans[i][1]=INF;
FOR(i,1,m)
{
x[i]=read(),y[i]=read();
g[x[i]][y[i]]=g[y[i]][x[i]]=1;
}
if(m==n-1)
{
dfs_1(1);
FOR(i,1,n) printf("%d ",ans[i][0]);
}
else {
FOR(t,1,m)
{
int i=x[t],j=y[t];
if(g[i][j])
{
memset(vis,0,sizeof(vis));
tot=flag=0;//变量一定要记得清零啊
g[i][j]=g[j][i]=0;
dfs_2(1);
g[i][j]=g[j][i]=1;
if(tot==n) FOR(k,1,n) ans[k][1]=ans[k][0];
}
}
FOR(i,1,n) printf("%d ",ans[i][1]);
}
return 0;
}
A、试题类型：
经典数学模型。
B、算法模型：
快速幂。
C、试题说明：
用搜索实现算法，并利用下面两个性质剪枝。外加快速幂解决问题。
题目中对矩阵的限制等价于如下两点：
(1) 、同一条副对角线上的元素单调不增。
(2) 、若同一条副对角线上相邻的两个位置相等，那么它们右下方的一个矩阵的每一条一条副对角线上的元素均相等。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 15;
const int P = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y)
{
x = max(x, y);
}
template <typename T> void chkmin(T &x, T y)
{
x = min(x, y);
}
template <typename T> void read(T &x)
{
x = 0; int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
int n, m, delta, ans, a[MAXN][MAXN];
bool same[MAXN][MAXN];
void work(int x, int y)
{
if (x == n + 1)
{
ans++;
return;
}
int tx = x, ty = y + 1;
if (ty >= m + 1) ty = 1, tx += 1;
for (int i = 0; i <= 1; i++)
{
if (i < a[x - 1][y + 1])
continue;
if (same[x - 1][y] && x - 1 >= 1 && y + 1 <= m && i != a[x - 1][y + 1])
continue;
a[x][y] = i, same[x][y] = a[x - 1][y] == a[x][y - 1] || same[x - 1][y] || same[x][y - 1];
work(tx, ty);
}
}
int power(int x, int y)
{
if (y == 0)
return 1;
int tmp = power(x, y / 2);
if (y % 2 == 0)
return 1ll * tmp * tmp % P;
else return
1ll * tmp * tmp % P * x % P;
}
int main()
{
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
read(n), read(m), delta = max(0, m - (n + 1));
chkmin(m, n + 1);
for (int i = 1; i <= n; i++)
a[i][0] = 8;
for (int i = 1; i <= m; i++)
a[0][i] = -8;
work(1, 1);
if (n == 1)
writeln(1ll * ans * power(2, delta) % P);
else
writeln(1ll * ans * power(3, delta) % P);
return 0;
}
A、试题类型：
混合题。
B、算法模型：
倍增 + 树形dp。
C、试题说明：
暴力dp，设f[i][0/1]表示i号点不选/选时i子树内的答案。
f[i][0]=Σf[son][1]，f[i][1]=a[i]+Σmin(f[son][0],f[son][1])。
倍增用法、倍增数组。floyd与矩乘。
另一种做法是dp。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define inf 100000000000ll
#define N 100010
char getc()
{
char c=getchar();
while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9'))
c=getchar();
return c;
}
int gcd(int n,int m)
{
return m==0?n:gcd(m,n%m);
}
int read()
{
int x=0,f=1;
char c=getchar();
while (c<'0'||c>'9')
{
if (c=='-') f=-1;c=getchar();
}
while (c>='0'&&c<='9')
x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,m,a[N],p[N],fa[N][18],deep[N],t;
ll f[N][2],g[N][18][2][2];
struct data
{
int to,nxt,len;
}edge[N<<1];
struct data2
{
ll x,y;int id;
};
void addedge(int x,int y)
{
t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;
}
void dfs(int k)
{
f[k][0]=0,f[k][1]=a[k];
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=fa[k][0])
{
deep[edge[i].to]=deep[k]+1;
fa[edge[i].to][0]=k;
dfs(edge[i].to);
f[k][0]+=f[edge[i].to][1];
f[k][1]+=min(f[edge[i].to][0],f[edge[i].to][1]);
}
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=fa[k][0])
{
g[edge[i].to][0][0][0]=inf;
g[edge[i].to][0][0][1]=f[k][1]-min(f[edge[i].to][0],f[edge[i].to][1]);
g[edge[i].to][0][1][0]=f[k][0]-f[edge[i].to][1];
g[edge[i].to][0][1][1]=f[k][1]-min(f[edge[i].to][0],f[edge[i].to][1]);
}
}
void pre()
{
for (int j=1;j<18;j++)
{
for (int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
for (int i=1;i<=n;i++)
for (int x=0;x<2;x++)
for (int y=0;y<2;y++)
g[i][j][x][y]=min(g[i][j-1][x][0]+g[fa[i][j-1]][j-1][0][y],g[i][j-1][x][1]+g[fa[i][j-1]][j-1][1][y]);
}
}
int lca(int x,int y)
{
if (deep[x]<deep[y])
swap(x,y);
for (int j=17;~j;j--)
if (deep[fa[x][j]]>=deep[y]) x=fa[x][j];
if (x==y)
return x;
for (int j=17;~j;j--)
if (fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
return fa[x][0];
}
data2 query(int x,int root,int isup,ll tx,ll ty)
{
data2 u;u.x=tx,u.y=ty;
for (int j=17;~j;j--)
if (deep[fa[x][j]]>deep[root])
{
tx=u.x,ty=u.y;
u.x=min(tx+g[x][j][0][0],ty+g[x][j][1][0]);
u.y=min(tx+g[x][j][0][1],ty+g[x][j][1][1]);
x=fa[x][j];
}
u.id=x;
if (isup)
{
tx=u.x,ty=u.y;
u.x=min(tx+g[x][0][0][0],ty+g[x][0][1][0]);
u.y=min(tx+g[x][0][0][1],ty+g[x][0][1][1]);
}
return u;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj5466.in","r",stdin);
freopen("bzoj5466.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read(),m=read();read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<n;i++)
{
int x=read(),y=read();
addedge(x,y),addedge(y,x);
}
fa[1][0]=1;dfs(1);
pre();
while (m--)
{
int x=read(),opx=read(),y=read(),opy=read();
if (deep[x]<deep[y])
swap(x,y),swap(opx,opy);
if (opx==0&&opy==0&&fa[x][0]==y)
{
printf("-1\n");
continue;
}
int k=lca(x,y);
if (k==y)
{
data2 u=query(x,k,0,opx==0?f[x][0]:inf,opx==1?f[x][1]:inf);
ll tx=u.x,ty=u.y;
u.x=f[k][0]+ty-f[u.id][1];
u.y=f[k][1]+min(tx,ty)-min(f[u.id][0],f[u.id][1]);
if (opy==0)
u.y=inf;
else
u.x=inf;
if (k!=1)
u=query(k,1,1,u.x,u.y);
printf(LL,min(u.x,u.y));
}
else
{
data2 u=query(x,k,0,opx==0?f[x][0]:inf,opx==1?f[x][1]:inf);
data2 v=query(y,k,0,opy==0?f[y][0]:inf,opy==1?f[y][1]:inf);
data2 w;
w.x=f[k][0]+u.y-f[u.id][1]+v.y-f[v.id][1];
w.y=f[k][1]+min(u.x,u.y)-min(f[u.id][0],f[u.id][1])+min(v.x,v.y)-min(f[v.id][0],f[v.id][1]);
w=query(k,1,1,w.x,w.y);
printf(LL,min(w.x,w.y));
}
}
return 0;
}
IT航班提供：教辅资料、课程视频、课程书籍、竞赛辅导、少儿编程指导、课程采购、加盟、少儿编程资料、少儿编程课程、保送生、特长生、加分、中小学计算机教育、中小学信息学、竞赛、中小学信息学课程、人工智能、中小学编程加盟、少儿编程加盟、品牌加盟、技术加盟、技术指导、课程加盟、师资培训、中小学编程教辅资料、中小学编程教师培训、少儿编程教学书籍、少儿编程视频、教学书籍、教师培训、教学视频、CSP-J/S、中小学信息学课程服务、竞赛指导、课程提供、国内外计算机中小学计算机竞赛、信息学竞赛、信息学课程提供商、信息学奥林匹克。
IT航班支持----中小学编程比赛汇总：
第一部分：国内比赛(IT航班支持)
1、软件能力认证(CSP-JS)
2、全国青少年信息学奥林匹克联赛(NOIP)
3、全国青少年信息学奥林匹克竞赛(NOI)
4、中国青少年………………………
5、………………………创新挑战赛
6、全国青少年………………………
7、………………………
8、 恩欧希教育信息化发明创新奖
9、世界机器人大赛(WRC)
10、………………………大赛
11、少………………………智能教育成果展示大赛
12、“明天小小科学家”奖励活动
13、………………………
14、………………………
15、国际信息学………………………
16、………………………
第二部分：国际比赛(IT航班支持)
17、………………………
18、国际………………………
19、………………………
20、美国信息学………………………
21、加拿大………………………
22、官方邀请赛 (CCO)
23、国际计算思维………………………
24、美国计算机………………………
25、澳大利亚………………………
第三部分：企业比赛(IT航班支持)
26、微软MTA
27、………………………挑战赛
28、………………………科学奖
29、………………………学奖
30、………………………创新挑战赛
31、………………………挑战赛
32、………………………芯计算机表演赛
33、………………………大赛
第四部分：Scratch相关竞赛(IT航班支持)
34、全国中小学生电脑制作大赛
35、………………………
36、………………………
37、………………………
第五部分：其它(IT航班支持)
38、NOI夏令营
39、NOI冬令营(NOIWC)
40、全国青少年………………………
41、国际青少年………………………
联系方式：
A、官方网址：
B、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
