首页 > 代码库 > 周赛2（星期三之前补题完）

周赛2（星期三之前补题完）

2024-08-02 12:17:04   219人阅读

本厂做了3个水体，被略哭

水题1  暴力乱搞

题目：

回文数猜想

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4433    Accepted Submission(s): 2638


Problem Description
一个正整数，如果从左向右读（称之为正序数）和从右向左读（称之为倒序数）是一样的，这样的数就叫回文数。任取一个正整数，如果不是回文数，将该数与他的倒序数相加，若其和不是回文数，则重复上述步骤，一直到获得回文数为止。例如：68变成154（68+86），再变成605（154+451），最后变成1111（605+506），而1111是回文数。于是有数学家提出一个猜想：不论开始是什么正整数，在经过有限次正序数和倒序数相加的步骤后，都会得到一个回文数。至今为止还不知道这个猜想是对还是错。现在请你编程序验证之。
 

Input
每行一个正整数。
特别说明：输入的数据保证中间结果小于2^31。
 

Output
对应每个输入，输出两行，一行是变换的次数，一行是变换的过程。
 

Sample Input
27228
37649
 

Sample Output
3
27228--->109500--->115401--->219912
2
37649--->132322--->355553
 

Author
SmallBeer(CML)
 

Source
杭电ACM集训队训练赛（VII）
 

Recommend
lcy   |   We have carefully selected several similar problems for you:  1279 1287 1276 1256 1250 
 

Statistic | Submit | Discuss | Note

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

const  int maxn=1000000;

int n,path[maxn];
char str[maxn],xx[maxn],yy[maxn];

bool isprime(int n)
{
    itoa(n,str,10);
    int len=strlen(str);
    for(int i=0;i<len/2;i++)
    {
        if(str[i]!=str[len-i-1])
            return false;
    }
    return true;
}

int main()
{
    int ok,cnt,temp;
    while(~scanf("%d",&n))
    {
        cnt=0;
        path[++cnt]=n;
        ok=1;
        while(ok)
        {
            if(!isprime(n))
            {
                 int zz=0;
                 itoa(n,xx,10);
                 int len=strlen(xx);
                 for(int i=len-1;i>=0;i--)
                 {
                     yy[zz]=xx[i];
                     zz++;
                 }
                 yy[zz]='\0';
                 n=n+atoi(yy);
                 path[++cnt]=n;
            }
            else
                ok=0;
        }
        printf("%d\n",cnt-1);
        for(int i=1;i<cnt;i++)
            printf("%d--->",path[i]);
        printf("%d\n",path[cnt]);
    }
    return 0;
}

题2：

UVA10954 ADD ALL（优先队列）

可以说是哈弗曼模型吧

就是给n个数，然后求n个数的和的和最小

就是构造一个数越小优先级越高的队列，每次取前两位，然后求累加和即可

题目：

Problem F
Add All
Input: standard input
Output: standard output

Yup!! The problem name reflects your task; just add a set of numbers. But you may feel yourselves condescended, to write a C/C++ program just to add a set of numbers. Such a problem will simply question your erudition. So, let’s add some flavor of ingenuity to it.

 

Addition operation requires cost now, and the cost is the summation of those two to be added. So, to add 1 and 10, you need a cost of11. If you want to add 1, 2 and 3. There are several ways –

 

1 + 2 = 3, cost = 3

3 + 3 = 6, cost = 6

Total = 9

1 + 3 = 4, cost = 4

2 + 4 = 6, cost = 6

Total = 10

2 + 3 = 5, cost = 5

1 + 5 = 6, cost = 6

Total = 11

 

I hope you have understood already your mission, to add a set of integers so that the cost is minimal.

 

Input

Each test case will start with a positive number, N (2 ≤ N ≤ 5000) followed by N positive integers (all are less than 100000). Input is terminated by a case where the value of N is zero. This case should not be processed.

 

Output

For each case print the minimum total cost of addition in a single line.

 

Sample Input                           Output for Sample Input

3

1 2 3

4

1 2 3 4

0

 

9

19

 

Problem setter: Md. Kamruzzaman, EPS


代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

const int maxn=5000+10;

priority_queue<int,vector<int>,greater<int> >Q;

int a[maxn],n;

int main()
{
    int last,ans;
    while(~scanf("%d",&n),n)
    {
        while(!Q.empty()) Q.pop();
        ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&last);
            Q.push(last);
        }
        for(int i=1;i<n;i++)
        {
            int a=Q.top();Q.pop();
            int b=Q.top();Q.pop();
            last=a+b;
            ans+=last;
            Q.push(last);
        }
        printf("%d\n",ans);
    }
    return 0;
}

下一个一个带条件的最小生成树，所以这个题目要想一下。。将毁坏的诚实标记一下，这杨就可以了

题目：

The plan of city rebuild

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 677    Accepted Submission(s): 233


Problem Description
News comes!~City W will be rebuilt with the expectation to become a center city. There are some villages and roads in the city now, however. In order to make the city better, some new villages should be built and some old ones should be destroyed. Then the officers have to make a new plan, now you , as the designer, have the task to judge if the plan is practical, which means there are roads(direct or indirect) between every two villages(of course the village has not be destroyed), if the plan is available, please output the minimum cost, or output"what a pity!".
 

Input
Input contains an integer T in the first line, which means there are T cases, and then T lines follow.
Each case contains three parts. The first part contains two integers l(0<l<100), e1, representing the original number of villages and roads between villages(the range of village is from 0 to l-1), then follows e1 lines, each line contains three integers a, b, c (0<=a, b<l, 0<=c<=1000), a, b indicating the village numbers and c indicating the road cost of village a and village b . The second part first contains an integer n(0<n<100), e2, representing the number of new villages and roads(the range of village is from l to l+n-1), then follows e2 lines, each line contains three integers x, y, z (0<=x, y<l+n, 0<=z<=1000), x, y indicating the village numbers and z indicating the road cost of village x and village y. The third part contains an integer m(0<m<l+n), representing the number of deserted villages, next line comes m integers, p1,p2,…,pm,(0<=p1,p2,…,pm<l+n) indicating the village number. 
Pay attention: if one village is deserted, the roads connected are deserted, too.
 

Output
For each test case, If all villages can connect with each other(direct or indirect), output the minimum cost, or output "what a pity!".
 

Sample Input
2
4 5
0 1 10
0 2 20
2 3 40
1 3 10
1 2 70
1 1
4 1 60
2
2 3
3 3
0 1 20
2 1 40
2 0 70
2 3
0 3 10
1 4 90
2 4 100
0
 

Sample Output
70
160
 

Author
wangjing
 

Source
HDU 2nd “Vegetable-Birds Cup” Programming Open Contest
 

Recommend
lcy   |   We have carefully selected several similar problems for you:  3081 3082 3087 3086 3079 
 
代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
priority_queue<int,vector<int>,greater<int> >Q;


const int maxn=1000+10;
bool vis[maxn];
int cnt,yy,root[maxn];

struct Edge
{
    int u,v,w;
}edge[maxn*maxn];

bool cmp(Edge a,Edge b)
{
    return a.w<b.w;
}

int findroot(int x)
{
    if(root[x]!=x)
        root[x]=findroot(root[x]);
    return root[x];
}

int kruscal(int n)
{
    for(int i=0;i<maxn;i++)
        root[i]=i;
    int l,r,ans=0;
    int xx=0;
    for(int i=1;i<=cnt;i++)
    {
        int l=edge[i].u;
        int r=edge[i].v;
        int val=edge[i].w;
        if(vis[l]||vis[r])
            continue;
        else
        {
            int fx=findroot(l);
            int fy=findroot(r);
            if(fx==fy)  continue;
            else
            {
                root[fx]=fy;
               // printf("%d %d %d\n",l,r,val);
                ans+=val;
                xx++;
                if(xx==n-1)
                    return ans;
            }
        }
    }
    return -1;
}

int main()
{
    int t,n,m,sum,l,r,mid,newc,newr,old;
    scanf("%d",&t);
    while(t--)
    {
        memset(vis,false,sizeof(vis));
        cnt=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&l,&r,&mid);
            edge[++cnt].u=l;
            edge[cnt].v=r;
            edge[cnt].w=mid;
           // printf("%d %d %d\n",l,r,mid);
        }
        scanf("%d%d",&newc,&newr);
        for(int i=1;i<=newr;i++)
        {
            scanf("%d%d%d",&l,&r,&mid);
            edge[++cnt].u=l;
            edge[cnt].v=r;
            edge[cnt].w=mid;
          //  printf("%d %d %d\n",l,r,mid);
        }
        scanf("%d",&old);
        for(int i=1;i<=old;i++)
        {
            scanf("%d",&l);
            vis[l]=true;
        }
        sort(edge+1,edge+1+cnt,cmp);
        int ans=kruscal(n+newc-old);
        if(ans==-1)  printf("what a pity!\n");
        else printf("%d\n",ans);
    }
    return 0;
}

第四个题目 哎 我真是too  young  too simple

我竟然看样例那个神奇的字母是B，然后就以为不变了  

哎  直接枚举A--Z看哪个字母满足条件即可，

题目：

破译密码

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3570    Accepted Submission(s): 1622


Problem Description
有个叫“猪头帮”的国家，采用一种简单的文法加密，他们所用的语言里面只有大写字母，没有其他任何字符；现在还知道他们加密的方法是：只用一个大写字母和原文进行异或运算生成密文。请你帮忙解开。
 

Input
有若干组，每组输入有2行，第一行整数N表示有N个密文，接着一行有N个整数分别表示N个密文。
 

Output
输出仅有大写字母组成的原文。
 

Sample Input
30
17 6 9 8 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 18 19 16 17 22 23 20 21 26 27 24
 

Sample Output
SDKJABCDEFGHIJKLMNOPQRSTUVWXYZ
 

Author
SmallBeer(CML)
 

Source
杭电ACM集训队训练赛（VII）
 

Recommend
lcy   |   We have carefully selected several similar problems for you:  1285 1279 1236 1201 1256 
 
z代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
priority_queue<int,vector<int>,greater<int> >Q;


const int maxn=10000+10;

int a[maxn],n;

int main()
{
    char ch;
    int i,j;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(i=0;i<26;i++)
        {
            ch=i+'A';
            for(j=1;j<=n;j++)
            {
                 if((a[j]^ch)<'A'||(a[j]^ch)>'Z')
                     break;
            }
            if(j==n+1)
                break;
        }
        //printf("%c\n",ch);
        for(int i=1;i<n;i++)
            printf("%c",ch^a[i]);
        printf("%c\n",ch^a[i]);
    }
    return 0;
}


周赛2（星期三之前补题完）


联系
我们