闲的蛋疼打了一场小白，然后被爆踩。。。
J题好难啊，要学了莫反才能做，先留坑吧
先放一发官方题解
小A的签到题
链接：https://ac.nowcoder.com/acm/contest/549/A
来源：牛客网
题目描述
这是一道签到题，主要考验比赛时的手速。
接下来是一段很简单的代码，或许你提交它就可以AC。
#include<bits/stdc++.h>
using namespace std;
int main() {
long long n;
scanf("%lld",&n);
long long f1=1,f2=1,f3;
for(int i=3;i<=n;i++) {
f3=f1+f2;
f1=f2;
f2=f3;
}
printf("%lld\n",f3*f3-f1*f1-f1*f3);
return 0;
}
输入描述:
一行一个整数N
输出描述:
一行一个整数表示结果
示例1
输入
3
输出
1
备注:
3≤N≤1e11
sol:XJB找找规律发现奇数是1，偶数是-1
#include <bits/stdc++.h> using namespace std; typedef long long ll; inline ll read() { ll s=0; bool f=0; char ch=' '; while(!isdigit(ch)) { f|=(ch=='-'); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) { if(x<0) { putchar('-'); x=-x; } if(x<10) { putchar(x+'0'); return; } write(x/10); putchar((x%10)+'0'); return; } #define W(x) write(x),putchar(' ') #define Wl(x) write(x),putchar('\n') ll n; int main() { R(n); if(n&1) puts("1"); else puts("-1"); return 0; }
View Code
链接：https://ac.nowcoder.com/acm/contest/549/B
来源：牛客网
小A的回文串
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
小A非常喜欢回文串，当然我们都知道回文串这种情况是非常特殊的。所以小A只想知道给定的一个字符串的最大回文子串是多少，但是小A对这个结果并不是非常满意。现在小A可以对这个字符串做一些改动，他可以把这个字符串最前面的某一段连续的字符(不改变顺序)移动到原先字符串的末尾。那么请问小A通过这样的操作之后(也可以选择不移动)能够得到最大回文子串的长度是多少。
输入描述:
一行一个字符串表示给定的字符串S
输出描述:
一行输出一个整数，表示通过这样的操作后可以得到最大回文子串的长度。
示例1
输入
复制
dcbaabc
输出
复制
7
说明
将前面的dcba移动到末尾变成abcdcba，这个字符串的最大回文子串就是它本身，长度为7
备注:
N表示字符串的长度，1≤N≤5000
sol:直接枚举断点，然后移过去，在之后马拉车可以n2过掉此题，但是我忘了马拉车怎么写，然后其实根本不用马拉车，把整个字符串复制一遍，粘在末尾，找到整个字符串的最长回文串就是答案了
#include <bits/stdc++.h> using namespace std; typedef int ll; inline ll read() { ll s=0; bool f=0; char ch=' '; while(!isdigit(ch)) { f|=(ch=='-'); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) { if(x<0) { putchar('-'); x=-x; } if(x<10) { putchar(x+'0'); return; } write(x/10); putchar((x%10)+'0'); return; } #define W(x) write(x),putchar(' ') #define Wl(x) write(x),putchar('\n') const int N=5005; int n; char S[N<<1]; int main() { int i,l,r,ans=0; scanf("%s",S+1); n=strlen(S+1); for(i=1;i<=n;i++) S[i+n]=S[i]; for(i=1;i<=2*n;i++) { l=i; r=i; while(S[l]==S[r]&&l>=1&&r<=2*n&&r-l+1<=n) l--,r++; ans=max(ans,r-l+1-2); l=i,r=i+1; while(S[l]==S[r]&&l>=1&&r<=2*n&&r-l+1<=n) l--,r++; ans=max(ans,r-l+1-2); } Wl(ans); return 0; } /* input dcbaabc output 7 */
View Code
链接：https://ac.nowcoder.com/acm/contest/549/C
来源：牛客网
小A买彩票
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
小A最近开始沉迷买彩票，并且希望能够通过买彩票发家致富。已知购买一张彩票需要3元，而彩票中奖的金额分别为1,2,3,4元，并且比较独特的是这个彩票中奖的各种金额都是等可能的。现在小A连续购买了n张彩票，他希望你能够告诉他至少能够不亏本的概率是多少。
输入描述:
一行一个整数N，为小A购买的彩票数量
输出描述:
输出一个最简分数a/b，表示小A不亏本的概率。若概率为1，则输出1/1，概率为0，则输出0/1。
示例1
输入
复制
2
输出
复制
3/8
备注:
30
sol:dp随便搞搞，dp[i][j]表示买了i张彩票，一共得了j元钱，转移十分水
#include <bits/stdc++.h> using namespace std; typedef long long ll; inline ll read() { ll s=0; bool f=0; char ch=' '; while(!isdigit(ch)) { f|=(ch=='-'); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) { if(x<0) { putchar('-'); x=-x; } if(x<10) { putchar(x+'0'); return; } write(x/10); putchar((x%10)+'0'); return; } #define W(x) write(x),putchar(' ') #define Wl(x) write(x),putchar('\n') const int N=35; int n; ll dp[N][N<<2]; inline ll gcd(ll a,ll b) { return (!b)?(a):(gcd(b,a%b)); } int main() { int i,j,k; R(n); dp[0][0]=1; for(i=0;i<n;i++) { for(j=i;j<=(i<<2);j++) { for(k=1;k<=4;k++) dp[i+1][j+k]+=dp[i][j]; } } ll Fz=0,Fm; for(i=((n<<1)+n);i<=(n<<2);i++) Fz+=dp[n][i]; Fm=1ll<<(n<<1); ll GG=gcd(Fz,Fm); write(Fz/GG); putchar('/'); Wl(Fm/GG); return 0; } /* input 2 output 3/8 */
View Code