传送门：https://www.nowcoder.com/acm/contest/90#question
A-跳台阶
规律题，就是2^n
D-psd面试
- 测试数据里可能有空行，gets输入贡献了好几发
- 求最长回文子序列长，可以考虑两种做法：
- 将原串复制一份并翻转，让后原串与反串做LCS
- 直接 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;elsecout<<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.1int 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;
}