41 盾神与条状项链
作者: Turbo 时间限制: 1S 章节: 模拟
问题描述 :
有一天，盾神捡到了好多好多五颜六色的珠子！他心想这些珠子这么漂亮，可以做成一条项链然后送给他心仪的女生~于是他用其中一些珠子做成了长度为n的项链。当他准备把项链首尾相接的时候，土方进来了。
“哇这么恶心的项链你也做得出来！！！”
盾神自知审美不是他的长项，于是他很谦虚地请教土方，怎么才能把项链做得漂亮。
“这个嘛首先你要在这里加上一个这种颜色的珠子，然后在这里去掉这个珠子，然后……，最后你看看是不是漂亮很多咧”土方一下子说出了m个修改步骤。
盾神觉得这个用人工做太麻烦了，于是交给了你。
输入说明 :
第一行两个数，分别为n，m。
第二行n个数，表示盾神一开始的项链。第i个数表示第i颗珠子的颜色。
接下来m行，为以下形式之一：
ADD P Q：表示在颜色为P的珠子前面加上一个颜色为Q的珠子。
DEL P：表示把颜色为P的珠子去掉，如果它不在端点处，则需要把它旁边的两颗珠子连起来。例如某时刻项链状态为1 4 5 8，则执行DEL 4会变成1 5 8，执行DEL 1会变成4 5 8。
输入保证在每次操作之前，项链有颜色为P的珠子，且任意时刻珠子颜色互不相同。
表示颜色的数字不超过105的正数，1<=n<=104，1<=m<=10^4。
输出说明 :
第一行为一个数len，为做完所有操作后，项链的长度。
第二行len个数，表示此时项链的状态。第i个数表示第i颗珠子的颜色。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>//链表操作
typedef struct nod
{
int data;
struct nod *next;
}node;
int n,m,len;
void init(node *&head)
{
node *p,*r;
head=(node*)malloc(sizeof(node));
head->next=NULL;
r=head;
len=n;
for(int i=0;i<n;++i)
{
p=(node*)malloc(sizeof(node));
scanf("%d",&(p->data));
p->next=NULL;
r->next=p;
r=p;
}
}
void add(node *head,int p,int q)
{
node *pre=head,*t;
while(pre->next->data!=p && pre->next)pre=pre->next;//找到p
t=(node *)malloc(sizeof(node));
t->data=q;
t->next=pre->next;
pre->next=t;
len++;
}
void del(node *head,int p)
{
node *pre=head,*t;
while(pre->next->data!=p)pre=pre->next;
t=pre->next;//肯定能找到 所以不用担心找不到
pre->next=pre->next->next;
free(t);
len--;
}
int main()
{
node *head; //怎能无表头呢
scanf("%d %d",&n,&m);
init(head);
while(m--)
{
char str[100];
int p,q;
scanf("%s",str);
if(strcmp(str,"ADD")==0)
{
scanf(" %d %d",&p,&q);
add(head,p,q);
}
if(strcmp(str,"DEL")==0)
{
scanf(" %d",&p);
del(head,p);
}
}
printf("%d\n",len);
while(head->next)
{
printf("%d ",head->next->data);
head=head->next;
}
return 0;
}
42 Cutting Chains
作者: Turbo 时间限制: 1S 章节: 深度优先搜索
问题描述 :
什么！Anna Locke最近买了几个链环，并且其中的一些链环连接到了一起。
Anna想要把这些链环拼组成连续的一段链。她把这些链环带到一个珠宝商那里，珠宝商告诉她合并这些链环的费用取决于必须打开和关上的环的数目。为了最小化这个费用，她小心地计算为了合并成一个单独的序列所需要打开的最小的环的数目。这个比她想象中更困难。请你为她解决这个问题。
输入说明 :
输入包含多组关于链环集合的描述，对于每一组。每个链环集合由一行用一个或多个空格隔开的数字表示。
每个描述由一个n开始，表示链环集合中环的数量。我们把这些环编号为1,2,…,n。
紧接着n后面的整数描述了哪些环连接在一起。每个连接由一对整数i，j（1<=i,j<=n并且i≠j）来描述，代表环i和环j连接，即一个穿过另一个。每个链环集合用一对-1 -1表示结束（-1 -1 不用进行计算）
输入用n=0表示结束，并且n=0不用进行计算
1<=n<=15
输出说明 :
对于每一个输入的链环集合，输出一行形如
Set N: Minimum links to open is M
N是测试数据的组号，M是最小需要打开然后关闭的次数来使所有环组成一条单独的链。
1<=i,j<=n并且i≠j
#include<stdio.h>
#include<string.h>
#define min(a,b) a<b?a:b
int n,num,maxn=20,edge[20][20],vis[20];
int branch(int x)//分支数目
{
for(int i=0;i<n;++i)
{
if(x&(1<<i))continue;
int cnt=0;
for(int j=0;j<n;++j)
{
if(x&(1<<j))continue;//已经打开的环
if(edge[i][j])++cnt;//若其与其他环相连+1
}
if(cnt>2)return 1;//大于0 结束
}
return 0;
}
int dfs(int s,int now,int pre)
{//now是当前环 pre是上一个
vis[now]=1;
for(int i=0;i<n;++i)
{
if((s&(1<<i)) || !edge[now][i] || i==pre)continue;//如果已经打开或者遇见自己就跳过
if(vis[i]||dfs(s,i,now))return 1;
}
return 0;
}
int circle(int x)
{
for(int i=0;i<n;++i)
{
if(x&(1<<i)||vis[i])continue;
++num;
if(dfs(x,i,-1))return 1;
}
return 0;
}
int cal(int x)
{//计算要打开的环的数量
return x==0?0:cal(x/2)+(x&1);
}
int solve()
{
int ans=n-1;//最多打开的数目
for(int i=0;i<(1<<n);++i)
{
memset(vis,0,sizeof(vis));
num=0;
if(branch(i)||circle(i))continue;//若有环或者分支大于2
//int temp=cal(i);
if(cal(i)>=num-1)ans=min(ans,cal(i));//如果能够连起来，就更新ans
}
return ans;
}
int main()
{
int cou=0;
while(scanf("%d",&n) && n)
{
memset(edge,0,sizeof(edge));
int x,y;
while(scanf("%d %d",&x,&y) && x+y>0)
{
edge[x-1][y-1]=1;
edge[y-1][x-1]=1;
}
printf("Set %d: Minimum links to open is %d\n", ++cou, solve());
}
return 0;
}
43 最少操作数
作者: Turbo 时间限制: 1S 章节: 基本练习（数组）
问题描述 :
数组A*有n个元素，初始全为0。你可以对数组进行两种操作：1、将数组中的一个元素加1；2、将数组中所有元素乘2。求将数组A从初始状态变为目标状态B所需要的最少操作数。
输入说明 :
第一行一个正整数n表示数组中元素的个数
第二行n个正整数表示目标状态B中的元素
n<=50，B[i]<=1000
输出说明 :
输出一行表示最少操作数
#include<iostream>
int a[55],n;//逆向考虑 如果是奇数就-1，方便除2呀，如果全是偶数/2
__int64 ans=0;
int judge()//判断是否全是0
{
for(int i=0;i<n;++i)
if(a[i]!=0)return 0;
return 1;
}
int main()
{
std::cin>>n;
for(int i=0;i<n;++i)
std::cin>>a[i];
while(1)
{
for(int i=0;i<n;++i)//是奇数就-1
if(a[i]&1){
a[i]--;
ans++;
}
if(judge())break;
for(int i=0;i<n;++i)a[i]/=2;
ans++;
}
std::cout<<ans<<std::endl;
return 0;
}
#include<stdio.h>
void printX(int b)
{
if(b!=0)
{
printf("x");
if(b!=1)printf("^%d",b);
}
}
int main()
{
int n,b;
scanf("%d %d",&n,&b);
if(b<0)printf("-");
if(b!=1 && b!=-1)printf("%d",b>0?b:-b);
printX(n);
while(--n>=0)
{
scanf("%d",&b);
if(b==0)continue;
printf(b>0?"+":"-");
if(n!=0 && b!=1 && b!=-1)printf("%d",b>0?b:-b);
printX(n);
}
if(b!=0)printf("%d",b>0?b:-b);
return 0;
}
#include<stdio.h>
int main()//和最大子序列，思路是动态规划，我们尽量使用连续的序列，因为
{//连续的才能遇见更好的（更大的数），那么假设dp[i-1]是i-1及其之前连续的和
long long int n,temp,max;//有可能a[i-1]是负的，但是没关系，只要加上a[i-1]后dp[i-1]还是正的
while(scanf("%lld",&n)!=EOF)
{//那么它这个状态就是一个略好的，我们到最后比较哪个dp[i]最大
scanf("%lld",&max);
long long int sum=max;//就是我们想要的结果，结果可能很大 要使用long int 刚刚就wa了
for(int i=1;i<n;++i)
{
scanf("%lld",&temp);
if(sum>=0)sum+=temp;//sum就是之前i-1个的状态，若他是正的或者0，则可以尽量和后面连续
else sum=temp;//若实在没办法。就只能从新加和
if(max<sum)max=sum;
}
printf("%lld\n",max);
}
return 0;
}
#include<stdio.h>
#define min(a,b) (a<b?a:b)//dfs+动态规划
int n,k,max=-1,ans[20],v[20];
void calculate()//计算当前组合得到的最大值
{
int dp[300]={0},i=0;//dp[i]是表示i面值 最少需要多少张
while(dp[i]<=n)//当张数还不满
{
++i;
dp[i]=99999;
for(int j=0;j<k && i>=v[j];++j)
dp[i]=min(dp[i],dp[i-v[j]]+1);
}//当无法连续时候才跳出循环 所以是i-1是答案
if(i-1>max)
{
max=i-1;
for(int i=0;i<k;++i) ans[i]=v[i];
}
}
void DFS(int deep)//搜索可能有的组合
{
if(deep==k-1)//这题很严格 一开始出口是k 就TLE了
{
calculate();
return;
}
for(int i=v[deep]+1;i<v[deep]*n+2;++i)//假设 前面是3 则 下一个设计最大是3*n+1 不然断了
{
v[deep+1]=i;
DFS(deep+1);
}
}
int main()
{
scanf("%d %d",&n,&k);
v[0]=1;//第一张肯定是1
DFS(0);
for(int i=0;i<k;++i)printf(i==0?"%d":" %d",ans[i]);
printf("\nMAX=%d\n",max);
return 0;
}
#include<stdio.h>
#include<string.h>
int convert(int x)
{
int sum=0;
while(x)
{
sum+=x%10;
x/=10;
}
return sum<10?sum:convert(sum);
}
int main()//好久没见过这种水题了，开心
{
char str[2020];
int n,code[6];
scanf("%d ",&n);
while(n--)
{
gets(str);
int len=strlen(str),y=0;
memset(code,0,sizeof(code));
for(int i=0;i<len;i++)
{
code[y]+=str[i];
y=(y+1)%6;
}
for(int i=0;i<6;++i)printf("%d",convert(code[i]));
printf("\n");
}
return 0;
}
48 小计算器
作者: Turbo 时间限制: 1S 章节: 模拟
问题描述 :
模拟程序型计算器，依次输入指令，可能包含的指令有
数字：‘NUM X’，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数
运算指令：‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’，分别表示加减乘，除法取商，除法取余
进制转换指令：‘CHANGE K’，将当前进制转换为K进制(2≤K≤36)
输出指令：‘EQUAL’，以当前进制输出结果
重置指令：‘CLEAR’，清除当前数字
指令按照以下规则给出：
数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出
运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
进制转换指令可能出现在任何地方
运算过程中中间变量均为非负整数，且小于2^63。
以大写的’A’'Z’表示1035
输入说明 :
第1行：1个n，表示指令数量
第2…n+1行：每行给出一条指令。指令序列一定以’CLEAR’作为开始，并且满足指令规则
输出说明 :
依次给出每一次’EQUAL’得到的结果
#include<stdio.h>
#include<string.h>//感觉使用运算时候都转成10进制比较好办
__int64 convert10(char s[],__int64 b)//b进制下的s换成10进制的
{
__int64 sum=0,temp=1,num;
int len=strlen(s)-1;
while(len>=0)
{
if(s[len]>='A')num=10+s[len]-'A';
else num=s[len]-'0';
sum+=num*temp;
temp=temp*b;
len--;
}
return sum;
}
void convert(__int64 x, __int64 b)//把10进制的x转换成b进制，除留余数法
{//输出
if(b==10){
printf("%I64d\n",x);
return;
}
int sta[5000],pos=-1;
do
{
sta[++pos]=x%b;
x/=b;
}while(x);//有效的解决了0的输出问题
while(pos!=-1)
{
if(sta[pos]<10)printf("%d",sta[pos]);
else printf("%c",sta[pos]-10+'A');
pos--;
}
printf("\n");
}
__int64 cal(__int64 a,__int64 b,__int64 flag)
{
if(flag==1)return a+b;
else if(flag==2) return a-b;
else if(flag==3) return a*b;
else if(flag==4) return a/b;
else if(flag==5) return a%b;
}
int main()
{
char str[2020],s1[2020];
__int64 n,temp,sum,k=10,flag=1;//flag表示+-...
scanf("%I64d",&n);
getchar();
while(n--)
{
scanf("%s",str);
getchar();
if(strcmp(str,"CLEAR")==0)
{
sum=0;//每次clear之后进制不变
flag=1;//初始的时候是+ 它不香吗
}
if(str[0]=='N' && str[1]=='U' && str[2]=='M')
{
scanf("%s",s1);
getchar();
temp=convert10(s1,k);
sum=cal(sum,temp,flag);
}
if(strcmp(str,"ADD")==0)flag=1;
if(strcmp(str,"SUB")==0)flag=2;
if(strcmp(str,"MUL")==0)flag=3;
if(strcmp(str,"DIV")==0)flag=4;
if(strcmp(str,"MOD")==0)flag=5;
if(str[0]=='C'&&str[1]=='H'&&str[2]=='A')
{
scanf("%I64d",&k);
getchar();
}
if(strcmp(str,"EQUAL")==0)convert(sum,k);
}
return 0;
}
49 合根植物
作者: Turbo 时间限制: 1S 章节: 深度优先搜索
问题描述 :
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体(也就是说，成为一株合根植物了）。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
输入说明 :
第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。
接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。
比如：5 * 4 的小格子，编号：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
比如输入：
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
其合根情况如下：
因此总共有5株合根植物。
#include<stdio.h>
int tree[1000001],m,n,k,a,b,x,y;//克鲁斯卡尔算法
int getroot(int a)
{
while(tree[a]!=a)
a=tree[a];
return a;
}
int main()
{
for(int i=0;i<1000001;++i)tree[i]=i;
scanf("%d %d %d",&m,&n,&k);
for(int i=0;i<k;++i)
{
scanf("%d %d",&a,&b);
x=getroot(a);
y=getroot(b);
if(x!=y)tree[x]=y;
}
int ans=0;
for(int i=1;i<=m*n;++i)
{
if(tree[i]==i)ans++;
}
printf("%d\n",ans);
return 0;
}
#include<iostream>
#include<algorithm>//深搜
int n,m,e[110][110],ans=10000;
int room[110][110];//room[i][0]表示第i个room里有多少人
void dfs(int deep,int num)//num是有几个屋子，deep表示第几人
{
if(num>=ans)return;//剪枝
if(deep==n+1)//第n+1个人，即是n个都安排完了
{
ans=std::min(ans,num);
return;
}
for(int i=1,j;i<=num;++i)
{
for(j=1;j<=room[i][0];++j)
{
if(e[deep][ room[i][j] ]==1)break;
}
if(j>room[i][0])//若都不认识，进房子
{
room[i][0]++;
room[i][j]=deep;
dfs(deep+1,num);
room[i][0]--;
}
}
//再开一间
num++;
room[num][0]++;
room[num][ room[num][0] ]=deep;
dfs(deep+1,num);
room[num][0]--;//回溯
}
int main()
{
std::cin>>n>>m;;
for(int i=0;i<m;++i)
{
int a,b;
std::cin>>a>>b;;
e[a][b]=e[b][a]=1;
}
dfs(0,0);
std::cout<<ans<<std::endl;
return 0;
}