题1 牛跑步（running）
【题目描述】 新牛到部队，CG 要求它们每天早上搞晨跑，从 A 农场跑到 B 农场。从 A 农场到 B 农场中有 n- 个路口，分别标上号，A 农场为 号，B 农场为 n 号，路口分别为 ...n- 号，从 A 农场到 B 农场有很多条路径可以到达，而 CG 发现有的路口是必须经过的，即每条路径都经过的路口，CG 要把它们记录下来，这样 CG 就可以先到那个路口，观察新牛们有没有偷懒，而你的任务就是找出所有必经路口。 【输入格式】 第一行两个用空格隔开的整数 n（≤n≤）和 e（≤e≤）。 接下来从第 到第 e+ 行，每行两个用空格隔开的整数 p 和 q，表示路口 p 和 q 之间有路径直达。 输入数据保证必经路口一定存在，并且每个路口都和 A 农场、B 农场相连通。 【输出格式】 第一行一个整数 m，表示必经路口的数目。 第二行按从小到大的顺序依次输出每个必经路口的编号，每两个数之间用一个空格隔 开。 注意：不包括起点和终点。 【输入样例】 【输出样例】
题目
tag:dfs
思路：如果一个点是必须经过的，我们要找到它，不妨逆向的考虑。如果它不存在，点1和点n将不会连通。可以用floyd但时间不能保证，所以选择dfs。这里要注意，做这道题不能用以往的dfs套路，也就是说不能回溯，防止超时。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#define maxn 2010
using namespace std;
int n,m,vis[maxn],cnt,ans[maxn],Ans,hl[maxn],f;
struct X{
int u,v,ne;
}e[maxn<<];
int read()
{
int x=,flag=;
char ch=getchar();
while(ch<''||ch>''){
if(ch=='-') flag=-;
ch=getchar();
}
while(ch>=''&&ch<=''){
x=x*+ch-'';
ch=getchar();
}
return x*flag;
}
void add(int x,int y)
{
e[++cnt].u=x;
e[cnt].v=y;
e[cnt].ne=hl[x];
hl[x]=cnt;
}
void dfs(int x)
{
if(vis[n]) return;
vis[x]=;
if(x==n) return;
for(int j=hl[x];j;j=e[j].ne){
int v=e[j].v;
if(!vis[v]) dfs(v);
}
}
int main()
{
//freopen("running.in","r",stdin);
//freopen("running.out","w",stdout);
int x,y;
scanf("%d%d",&n,&m);
for(int i=;i<=m;++i){
x=read();y=read();
add(x,y);
add(y,x);
}
for(int i=;i<n;++i){
memset(vis,,sizeof(vis));
vis[i]=;
f=;
dfs();
if(!vis[n]){
ans[i]=;
Ans++;
}
vis[i]=;
}
printf("%d\n",Ans);
for(int i=;i<=n;++i) if(ans[i]) printf("%d ",i);
return ;
}
题 2 陈老师搬书(book.pas/c/cpp)
【问题描述】 陈老师喜欢网购书籍,经常一次购它个百八十本,然后拿来倒卖,牟取暴利。前些天,高一的新同学来了,他便像往常一样,兜售他的书,经过一番口舌,同学们决定买他的书,但是 CS 桌上的书有三堆,每一堆都有厚厚的一叠,他要想个办法用最轻松的方式把书拿下来给同学们.但是你想逗一下 CS，于是,请你设计一个最累的方式给他. 若告诉你这三堆分别有 i,j,k 本书,以及每堆从下到上书的重量.每次取书只能从任意一堆的最上面取,那么请你帮助他设计一个方案,让他花最大的力气取下所有书(CS 别打我). 显然,每次取书,陈老师的体力消耗都会加大,这里用体力系数代表,取下第一本书时,体力系数为 ,第二本时为 ,依次类推,而每次体力消耗值则为体力系数和书的重量之积。 举个例子: 三堆书及重量如下 （配图在外） 不用证明,最累的取书方式为: 右左左中, 即: *+*+*+*=+++= 【输入文件】（book.in） 输入文件的第一行为 个数,分别为三堆数量 I,j,k 第二行至第四行分别为每堆由下至上的书本重量 【输出文件】（book.out） 输出最累方式的体力消耗总值即可 【输入样例】 【输出样例】 【注释】: 输入数据为每堆由下至上的书本重量! 【数据规模】 对于 %的数据有:<=i< <=j< <=k< 对于 %的数据有:<=i< <=j< <=k< 最后输出的体力消耗总值在 longint 范围内
题目
tag:背包DP
思路：一道比较基础的DP，需要准确找到继承关系。我们用f[i][j][k]表示选择i本第一堆的书+j本+k本的最优解，可得dp方程f[i][j][k]=max(f[i][j][k],f[i-1][j][k]+a1[i]*(i+j+k),f[i][j-1][k]+a2[j]*(i+j+k),f[i][j][k-1]+a3[k]*(i+j+k));书的选择有先决条件（它上面的必须已经被选）当然不能用贪心，可以举反例来验证。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
using namespace std;
long f[][][];
int a1[],a2[],a3[],k1,k2,k3,i,j,k;
int main()
{
//freopen("book.in","r",stdin);
//freopen("book.out","w",stdout);
scanf("%d%d%d",&k1,&k2,&k3);
for(i=k1;i>;--i) scanf("%d",&a1[i]);
for(i=k2;i>;--i) scanf("%d",&a2[i]);
for(i=k3;i>;--i) scanf("%d",&a3[i]);
for(i=;i<=k1;++i)
for(j=;j<=k2;++j)
for(k=;k<=k3;++k){
if(i>=) f[i][j][k]=max(f[i][j][k],f[i-][j][k]+a1[i]*(i+j+k));
if(j>=) f[i][j][k]=max(f[i][j][k],f[i][j-][k]+a2[j]*(i+j+k));
if(k>=) f[i][j][k]=max(f[i][j][k],f[i][j][k-]+a3[k]*(i+j+k));
}
printf("%ld\n",f[k1][k2][k3]);
return ;
}
题 3 背单词(words)
【问题描述】 英语四级考试临近了，小 Y 却发现他已经把以前学的单词几乎忘光了。好在现在离考试还有一段时间，小 Y 决定从现在开始夜以继日地背单词。也就是说小 Y 废寝忘食，一天二十四小时地背单词。 今天的日期(时间)是 YYYY 年 mm 月 dd 日 hh 时 min 分，考试的时间是 YYYY’年 mm’月dd’日 hh’时 min’分。这之间的所有时间小 Y 都用来背单词了，那么考试之前他最多能背多少个单词呢? 时间紧张，小 Y 只管数量不管质量。当然有的单词长一些，有的单词短一些。长的单词难背一些，短的单词好背一些。根据小 Y 的经验，他能一眼看出背某一个单词需要的时间，以分钟记。 现在给你一个字典，请你挑出最多的单词使小 Y 能在考试前背出来。【输入格式】 第一行一个整数 N，表示字典中的单词数，N<=。 接下来 N 行，每行一个整数表示背这个单词需要用的时间，以分钟记，小于等于 。(这个单词本身是什么并不重要，不是吗?当前小 Y 已经认识的单词数为 个)。 接下来两行依次是当前时问和考试时间。时间给出的格式是:yyyy-mm-dd-hh:min.例 如:---:，采用 小时制，每天从 :-:，年份从 到 。 【输出格式】 一行一个数，表示考试前小 Y 最多能背出的单词数:【输入样例】 ---: ---: 【样例输出】
题目
tag:模拟 贪心
思路：直接算两个点的时间差需要无数个特判，难度太大，应转为从0000年的起始时间点开始计算，取整年整月比较好算。注意闰年。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
priority_queue<int>Q;
int cnt,n,x,ans,yue[]={,,,,,,,,,,,,},run[],c[];
long long t,t1,t2;
struct X
{
int year,month,day,hour,min;
}a,b;
int read()
{
int x=,flag=;
char ch=getchar();
while(ch<''||ch>''){
if(ch=='-') flag=-;
ch=getchar();
}
while(ch>=''&&ch<=''){
x=x*+ch-'';
ch=getchar();
}
return x*flag;
}
void dabiao()
{
for(int i=;i<=;++i)
if(i%==){
run[i]=;
if((i%==)&&(i%!=)) run[i]=;
}
}
void work()
{
t1=t2=;
for(int i=;i<a.year;++i) t1+=(+run[i])*;
for(int i=;i<a.month;++i) t1+=yue[i]*;
t1+=(a.day-)*;
t1+=a.hour*;
t1+=a.min;
for(int i=;i<b.year;++i) t2+=(+run[i])*;
for(int i=;i<b.month;++i) t2+=yue[i]*;
t2+=(b.day-)*;
t2+=b.hour*;
t2+=b.min;
t=t2-t1;
}
int main()
{
//freopen("words.in","r",stdin);
//freopen("words.out","w",stdout);
dabiao();
scanf("%d",&n);
for(int i=;i<=n;++i) scanf("%d",&c[i]);
sort(c+,c+n+);
a.year=read();a.month=read();a.day=read();a.hour=read();a.min=read();
b.year=read();b.month=read();b.day=read();b.hour=read();b.min=read();
work();
for(int i=;i<=n;++i){
if(t>=c[i]) ans++;
else break;
t-=c[i];
}
cout<<ans<<endl;
return ;
}
题 4 征兵
【问题描述】 小 W 拥有一个国家，现在他希望建立一支军队来保护他的国家。他选中了 N 个女孩和 M 个男孩希望招募他们成为他的士兵。在没有任何先决条件的情况下，他招募一个士兵需要花费 10000RMB。现在小 W 可以利用这些人之间的关系来减少他的花费。如果女孩 X 和男孩 Y 存在有一个关系值 D（两人之间可能有多个关系值），而且她们之中有一个人被招募了。那么小 W 可以在招募另一个人的时候减少 D 的花费（实际 -D 的费用）。 现在给你这些男孩女孩之间的关系，希望你告诉小 W 告诉他招募所有人的最少花费。注意：招募某一个人时，只能利用一个关系。 【输入格式】 输入文件 conscription.in 中文件第一行包含三个整数 N，M，R。表示 N 个女孩，M 个男孩与 R 条关系。 接下来 R 行，每行包含三个整数 Xi，Yi 和 Di，表示女孩 Xi 和男孩 Yi 有 Di 的关系。 【输出格式】 conscription.out 中只有一行一个数为最小费用。 【输入输出样例】 conscription.in conscription.out 【数据规模】 %的数据:<=N, M<=，<=R<=,， <di<
题目
tag:最小生成树
思路：kruscal求最小生成树，稍作处理得出答案。可以用10000*人数再减去所有生成树的边权，也可以像我这样最后查祖先数，每个祖先要花费10000的钱。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#define maxn 100010
using namespace std;
long long ans;
int cnt,fa[maxn<<],n,m,r,i,x,y,d,tot;
struct X{
int u,v,w;
}e[maxn<<];
void add(int x,int y,int w)
{
e[++cnt].u=x;
e[cnt].v=y;
e[cnt].w=w;
}
int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool cmp(X a,X b)
{
return a.w<b.w;
}
int main()
{
//freopen("conscription.in","r",stdin);
//freopen("conscription.out","w",stdout);
scanf("%d%d%d",&n,&m,&r);
for(i=;i<n+m;++i) fa[i]=i;
for(i=;i<=r;++i){
scanf("%d%d%d",&x,&y,&d);
add(x,y+n,-d);
add(y+n,x,-d);
}
sort(e+,e+cnt+,cmp);
for(i=;i<=cnt;++i){
int u=e[i].u,v=e[i].v,w=e[i].w;
int k1=find(u),k2=find(v);
if(k1!=k2){
fa[k1]=k2;
ans+=w;
tot++;
}
if(tot+==n+m) break;
}
cnt=;
for(i=;i<n+m;++i) if(fa[i]==i) cnt++;
ans+=cnt*;
cout<<ans<<endl;
return ;
}
┈━═┈━═┈━═┈━═┈━═┈━═┈━═┈━═依旧华丽的分割线┈━═┈━═┈━═┈━═┈━═┈━═┈━═┈━═☆
芒果君：这次考试比上次高了10分啊233333333我居然进步了（不）。本来准备昨天下午写解题报告结果一直浪到现在OTZ考试的话还是比较缺乏经验，好多分都没拿到，而且还出了freopen里words写成book的爆0*QAQ 不过下次也要加油哦~