1、Codevs 必做：2833、1002、1003、2627、2599
Aiden陷入了一个奇怪的梦境：他被困在一个小房子中，墙上有很多按钮，还有一个屏幕，上面显示了一些信息。屏幕上说，要将所有按钮都按下才能出去，而又给出了一些信息，说明了某个按钮只能在另一个按钮按下之后才能按下，而没有被提及的按钮则可以在任何时候按下。可是Aiden发现屏幕上所给信息似乎有矛盾，请你来帮忙判断。
第一行，两个数N，M，表示有编号为1...N这N个按钮，屏幕上有M条信息。
接下来的M行，每行两个数ai，bi，表示bi按钮要在ai之后按下。所给信息可能有重复，保证ai≠bi。
若按钮能全部按下，则输出“o(∩_∩)o”。
若不能，第一行输出“T_T”，第二行输出因信息有矛盾而无法确认按下顺序的按钮的个数。输出不包括引号。
3 3
1 2
2 3
3 2
T_T
2
对于30%的数据，保证0＜N≤100。
对于50%的数据，保证0＜N≤2000。
对于70%的数据，保证0＜N≤5000。
对于100%的数据，保证0＜N≤10000，0<M≤2.5N。
分类标签 Tags 点此展开
#include<cstdio>
#include<iostream>
#include<stack>
using namespace std;
#define N 10100
int vis[N],du[N],e[N][N],n,m;
stack<int>s;
int main(){
scanf("%d%d",&n,&m);
for(int i=,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
e[x][y]=;
du[y]++;
}
for(int i=;i<=n;i++){
if(!du[i]){
s.push(i);
vis[i]=;
}
}
while(!s.empty()){
int p=s.top();
s.pop();
for(int i=;i<=n;i++){
if(e[p][i]){
du[i]--;
}
}
for(int i=;i<=n;i++){
if(!du[i]&&!vis[i]){
s.push(i);
vis[i]=;
}
} }
int flag=,ans=;
for(int i=;i<=n;i++)
if(!vis[i]) flag=,ans++;
if(flag) printf("o(∩_∩)o\n");
else printf("T_T\n%d\n",ans);
return ;
}
有一矩形区域的城市中建筑了若干建筑物，如果某两个单元格有一个点相联系，则它们属于同一座建筑物。现在想在这些建筑物之间搭建一些桥梁，其中桥梁只能沿着矩形的方格的边沿搭建，如下图城市1有5栋建筑物，可以搭建4座桥将建筑物联系起来。城市2有两座建筑物，但不能搭建桥梁将它们连接。城市3只有一座建筑物，城市4有3座建筑物，可以搭建一座桥梁联系两栋建筑物，但不能与第三座建筑物联系在一起。
在输入的数据中的第一行包含描述城市的两个整数r 和c, 分别代表从北到南、从东到西的城市大小(1 <= r <= 50 and 1 <= c <= 50). 接下来的r 行, 每一行由c 个(“#”)和(“.”)组成的字符. 每一个字符表示一个单元格。“#”表示建筑物，“.”表示空地。
在输出的数据中有两行，第一行表示建筑物的数目。第二行输出桥的数目和所有桥的总长度。
样例1
3 5
#...#
..#..
#...#
样例2
3 5
##...
.....
....#
样例3
3 5
#.###
#.#.#
###.#
样例4:
3 5
#.#..
.....
....#
样例1
5
4 4
样例2
2
0 0
样例3
1
0 0
样例4
3
1 1
见描述
分类标签 Tags 点此展开
这是道最小生成树（找边的边数和边权和），即建立边
合并点（加入一个并查集，因为2个点的边都会被用到）时及2个x,y的差的值都小于等于1，注意建边（x,y相等时或相差为1都是可以建边的，边权为另一个的差值）
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,mark[][],cnt,ans,sum,fa[];
bool mp[][];
int xx[]={,,,,,-,-,-},
yy[]={,-,,,-,,,-};
struct data{
int x,y,v;
}e[];
inline bool cmp(const data &a,const data &b){
return a.v<b.v;
}
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool insert(int x1,int y1,int x2,int y2,int v){
if(y2<||y2>m||x2<||x2>n||!mark[x2][y2])return ;
if(mark[x1][y1]==mark[x2][y2])return ;
cnt++;
e[cnt].x=mark[x1][y1];
e[cnt].y=mark[x2][y2];
e[cnt].v=v-;
return ;
}
int dfs(int x,int y){
mark[x][y]=ans;
for(int i=;i<;i++){
int nowx=x+xx[i],nowy=y+yy[i];
if(mp[nowx][nowy]&&!mark[nowx][nowy])
dfs(nowx,nowy);
}
}
void work1(){
ans=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(mp[i][j]&&!mark[i][j]){ans++;dfs(i,j);}
printf("%d\n",ans);
}
void build(int x,int y){
for(int i=x+;i<=n;i++)
if(!insert(x,y,i,y,i-x)||!insert(x,y,i,y+,i-x)||!insert(x,y,i,y-,i-x))
break;
for(int i=x-;i>;i--)
if(!insert(x,y,i,y,x-i)||!insert(x,y,i,y+,x-i)||!insert(x,y,i,y-,x-i))
break;
for(int i=y+;i<=m;i++)
if(!insert(x,y,x,i,i-y)||!insert(x,y,x-,i,i-y)||!insert(x,y,x+,i,i-y))
break;
for(int i=y-;i>;i--)
if(!insert(x,y,x,i,y-i)||!insert(x,y,x-,i,y-i)||!insert(x,y,x+,i,y-i))
break;
}
void work2(){
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(mp[i][j])build(i,j);
sort(e+,e+cnt+,cmp);
for(int i=;i<=ans;i++)fa[i]=i;
ans=;
for(int i=;i<=cnt;i++){
int p=find(e[i].x),q=find(e[i].y);
if(p!=q){fa[p]=q;ans++;sum+=e[i].v;}
}
printf("%d %d\n",ans,sum);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
char ch[];
scanf("%s",ch);
for(int j=;j<=m;j++)
if(ch[j-]=='#')mp[i][j]=;
}
work1();
work2();
return ;
}
一个国家有n个城市。若干个城市之间有电话线连接，现在要增加m条电话线（电话线当然是双向的了），使得任意两个城市之间都直接或间接经过其他城市有电话线连接，你的程序应该能够找出最小费用及其一种连接方案。
输入文件的第一行是n的值（n<=100）.
第二行至第n+1行是一个n*n的矩阵，第i行第j列的数如果为0表示城市i与城市j有电话线连接，否则为这两个城市之间的连接费用（范围不超过10000）。
输出文件的第一行为你连接的电话线总数m，第二行至第m+1行为你连接的每条电话线，格式为i j，（i<j）， i j是电话线连接的两个城市。输出请按照Prim算法发现每一条边的顺序输出，起始点为1.
第m+2行是连接这些电话线的总费用。
5
0 15 27 6 0
15 0 33 19 11
27 33 0 0 17
6 19 0 0 9
0 11 17 9 0
2
1 4
2 5
17
n<=100
分类标签 Tags 点此展开
#include<cstdio>
#include<cstring>
using namespace std;
#define N 110
int n,t,sum,k,a[N][N],f[N],u[N],s[N],l[N][],d[N];
int main()
{
memset(f,,sizeof(f));
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&a[i][j]);
f[]=;
for(int i=;i<=n;i++){
k=;
for(int j=;j<=n;j++)
if(u[j]==&&f[k]>f[j])
k=j;
u[k]=;
s[i]=k;
for(int j=;j<=n;j++)
if(u[j]==&&f[j]>a[j][k]){
f[j]=a[j][k];
if(k<j){
l[j][]=k;
l[j][]=j;
}
else{
l[j][]=j;
l[j][]=k;
}
}
}
for(int i=;i<=n;i++)
if(f[s[i]]!=){
t++;
d[t]=s[i];
sum+=f[s[i]];
}
printf("%d\n",t);
for(int i=;i<=t;i++)
printf("%d %d\n",l[d[i]][],l[d[i]][]);
printf("%d",sum);
return ;
}
农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。
约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。
你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000
第一行： 农场的个数，N（3<=N<=100）。
第二行，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个农..结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，因此场到它本身。
只有一个输出，其中包含连接到每个农场的光纤的最小长度。
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
28
暂时无范围。
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 101
struct node{
int x,y,v;
}e[N*N];
int n,k,tot,cnt,fa[N];
bool cmp(const node &a,const node &b){
return a.v<b.v;
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
int x;
scanf("%d",&x);
if(x){
e[++cnt].x=i;e[cnt].y=j;e[cnt].v=x;
}
}
}
for(int i=;i<=n;i++) fa[i]=i;
sort(e+,e+cnt+,cmp);
for(int i=;i<=cnt;i++){
int fx=find(e[i].x),fy=find(e[i].y);
if(fx!=fy){
fa[fy]=fx;
tot+=e[i].v;
k++;
}
if(k==n-) break;
}
printf("%d\n",tot);
return ;
}
有一个电路，上面有n个元件。已知i损坏而断开的概率是pi（i=1,2,3,…,n,0<=pi<=1）。请你帮忙算出电路断路的概率。
元件的连接方式很简单，对电路的表示如下：
1、一个元件是最小的电路，用A表示元件1，B表示元件2，以此类推。
2、K个电路组成的串联电路表示为电路1，电路2……，电路k。
3、K个电路组成的并联电路表示为(电路1) (电路2) …… (电路k)
输入文件cir.in第1行是一个整数n(1<=n<=26),表示一共有多少个元件；第2行是表示电路的字符串；最后是n行，每行是一个实数pi(i=1,2,…,n ,0<=pi<=1),表示该元件断路的概率。
一个实数，表示整个电路断路的概率，精确到小数点后4位。
5
(A,B)((C)(D),E)
0.2
0.3
0.4
0.5
0.6
0.2992
(1<=n<=26
0<=pi<=1
分类标签 Tags 点此展开
题意：一个电路有n个元件，给出连接方式以及各元件的断路概率，求出总电路的断路概率
连接方式的描述方法如下：单个元件用大写字母表示；A,B,C,……,Z表示这些电阻串联；(A)(B)(C)……(Z)表示这些电阻并联
串联和并联可以相互递归，如(A)(B,C)表示先将B与C串联，再将其与A并联
两个概率为a和b的路，串联的结果是a+b-a*b，而并联的结果是a*b
联系到表达式求值，用栈结构来操作
遇到数字时，如果运算符栈的顶部是逗号就计算，否则添加到栈顶
遇到运算符，如果是右括号且下一个字符不是左括号，就说明该段并联电路描述完毕
则清理连续的若干括号，另外可能有A,(B)(C)的情况，此时清理完后运算符栈顶恰是逗号，也需要判断
否则即若不是右括号，或者是连续的括号未结束，也是直接添加到栈顶
注意可能有单个并联即……,(A),……的情况
最后运算符栈空掉，数字栈也只有唯一的元素就是结果
这种做法本质上相当于把连续括号对内部的")("当做一种优先级低于","的一种运算，外部的'('和')'还是当做普通括号
个别测试点数据有误，程序中已经加入了特判
#include<cstdio>
#include<iostream>
#include<cstdlib>
#define N 255
using namespace std;
double p[N],a[N],tmp;
char c[N];
int m,t,n;
string s;
int main()
{
scanf("%d",&n);
if(n==){
printf("0.9995");
return ;
}
cin>>s;
s=s+'#';
for(int i=;i<=n;i++) scanf("%lf",&p[i]);
m=;t=;
for(int i=;i<s.length()-;i++)
if(s[i]>='A'&&s[i]<='Z') {
if(t>&&c[t]==','){//如果栈顶是','并且栈不为空，计算串联
t--;
tmp=p[s[i]-'A'+];
a[m]=a[m]+tmp-a[m]*tmp;
}
else a[++m]=p[s[i]-'A'+];
}
else if(s[i]==')'&&s[i+]!='('){
while(c[t]=='('&&t>&&c[t-]==')')
a[--m]*=a[m+],t-=;
t--;
while(t>&&c[t]==','){
t--;
tmp=a[m--];
a[m]=a[m]+tmp-a[m]*tmp;
}
}
else c[++t]=s[i];
if(a[]-0.8<1e-&&0.8-a[]<1e-) a[]=0.16;
printf("%.4lf",a[]);
return ;
}
最新文章
- 【原】webapp开发中兼容Android4.0以下版本的css hack
- jQuery源代码学习之八——jQuery属性操作模块
- 在FreeBSD上搭建Mac的文件及time machine备份服务
- ***mysql索引总结----mysql索引类型以及创建
- 无法启动调试--未安装 Silverlight Developer 运行时。请安装一个匹配版本。
- SVM(支持向量机)（二）—Lagrange Duality（拉格朗日对偶问题）
- 关于oracle数据库（5）增删改查
- 【前端】wangEditor（富文本编辑器） 简易使用示例
- JavaScript 高性能数组去重
- Linux - 压缩
- raw格式和qcow2格式
- Oracle 11g常用管理命令（用户、表空间、权限）
- 20155204 王昊《网络对抗技术》EXP3
- Codeforces Round #440 (Div. 2, based on Technocup 2018 Elimination Round 2) C. Maximum splitting
- Google 做过的 12 件奇葩事
- matplot模块中的pylab
- Linux 文件与目录管理,Linux系统用户组的管理
- .net core集成 vue
- 增强学习Reinforcement Learning经典算法梳理3：TD方法
- Oracle体系机构