博客

传送门：

https://www.nowcoder.com/acm/contest/90#question

A-跳台阶

规律题，就是2^n

D-psd面试

• 测试数据里可能有空行，gets输入贡献了好几发
• 求最长回文子序列长，可以考虑两种做法：
  
  1. 将原串复制一份并翻转，让后原串与反串做LCS
  2. 直接 DP
• 此处贴上DP代码

#include <iostream>  
#include <cstring>  
using namespace std;  

#define MAX 1300  
#define max(a,b) (a)>(b)?(a):(b)  

int f[2][MAX]={0};  

void LPS_Length(char *s,int len)
{
    memset(f, 0, sizeof(f));
    int flag=0;
    for (int i=len-1;i>=0;i--)  
    {  
        f[flag][i]=1;  
        for (int j=i+1;j<len;j++)
        {
            if(s[i]>='A'&&s[i]<='Z') s[i]=s[i]+'a'-'A';
            if(s[j]>='A'&&s[j]<='Z') s[j]=s[j]+'a'-'A';
            if (s[i]==s[j])         
                f[flag][j]=f[1-flag][j-1]+2;
            else        
                f[flag][j]=max(f[flag][j-1],f[1-flag][j]);      
        }
        flag=1-flag;
    }       
}
char str[MAX];
int main()  
{  
        //while(gets(str))
        while(~scanf("%s", str))
        {
            int len=strlen(str);
            LPS_Length(str,len);
            if(len%2 == 0)
                cout<<len - f[1][len-1]<<endl;
            else
                cout<<len - f[0][len-1]<<endl;
        }
    return 0;  
}

G-旋转矩阵

读取命令后，LR各%4，然后都转换成向右旋转操作，模拟一波

I-填空

好多水，然而刚开始并没有鉴别出水题

J-强迫症的序列

很巧妙的题！

逆向思维，n-1个数+1<=>最大的那个数-1

此时问题有转换成序列中的数最终都减到最小的那个数

#include <bits/stdc++.h>
#define I(a) scanf("%d", &a)
#define O(a) printf("%d", a)
using namespace std;
typedef long long LL;

const int maxn = 100005;
LL a[maxn];
int t, n;

int main()
{
    I(t);
    while(t--)
    {
        I(n);
        for(int i=0;i<n;i++) I(a[i]);
        sort(a, a+n);
        LL cnt = 0;
        for(int i=1;i<n;i++)
        {
            cnt+=a[i]-a[0];
         }

        printf("%lld %lld\n", cnt, cnt+a[0]);
    }
    return 0;
}

K-密码

用具体的n取小值，列举出来找规律。不要抽象的用n。

#include <bits/stdc++.h>
#define I(a) scanf("%d", &a)
#define O(a) printf("%c", a)
using namespace std;

char str[100005];

int main()
{
    int t, n;
    I(t);
    while(t--)
    {
        I(n);
        scanf("%s", str+1);
        if(n==1) 
        {
            printf("%s\n", str+1); continue;
        }
        int len = strlen(str+1);
        int d = 2*n-2;
        for(int i=1; i<=min(n, len); i++)
        {
            int pos = i;
            while(pos<=len)
            {
                if(i==1 || i==n)
                {
                    O(str[pos]);
                }
                else{
                    O(str[pos]);
                    if(pos+2*(n-i)<=len) O(str[pos+2*(n-i)]);
                }
                pos+=d;
            }
        }
        puts("");
    }
    return 0;
}

L-用来作弊的药水

一个神奇的精度问题

#include <bits/stdc++.h>
#define I(a) scanf("%d", &a)
#define O(a) printf("%d", a)
using namespace std;
typedef long long LL;
const double eps= 1e-4;  //1e-6时就不能全部case通过，此题精度粗点就可以，0.1

int a, x, y, b;

int main()
{

    int t;I(t);
    while(t--)
    {
        I(x), I(a), I(y), I(b);
        double m, n;
        m = a*log(x);
        n = b*log(y);
        if(abs(m-n)<=eps) puts("Yes");
        else puts("No");
    }
    return 0;
}

还见到了一个神奇的提交

#include <bits/stdc++.h>
#define I(a) scanf("%d", &a)
#define O(a) printf("%d", a)
using namespace std;

int main()
{
    int t, x, a, y, b;
    long long n, m;
    I(t);
    while(t--)
    {
        I(x), I(a), I(y), I(b);
        n=a*log10(x);   //改为log就不能通过所有case，函数的精度问题
        m=b*log10(y);
        if(m==n) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

补充一个

#include <bits/stdc++.h>
#define I(a) scanf("%lld", &a)
#define O(a) printf("%d", a)
using namespace std;

int main()
{
    int t;
    double x, a, y, b;
    I(t);
    while(t--)
    {
        scanf("%lf%lf%lf%lf", &x, &a, &y, &b);
        if(pow(x, a/b)==y || pow(y, b/a)==x) puts("Yes");
        else puts("No");
    }
    return 0;
}