牛客小白91
Bingbong的回文路径
https://ac.nowcoder.com/acm/contest/78807/G
原博客链接：https://blog.nowcoder.net/n/8f19b66f4bc14263958b1c3c398274df
第一次内测小白，记录一下
A
模拟。
import java.io.*;
import java.util.*;
public class Main{
static int maxn = 200005,n,m,inf=0x3fffffff;
static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
static Scanner sc = new Scanner (System.in);
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65536);
static StreamTokenizer st =new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[]args) throws IOException{
new Task().main();
pw.flush();
}
static class Task{
void main() throws IOException {
int T=1;
//T=I();
while(T-->0) solve();
}
String a = "...|......_...../.\\....|.|....\\_/\\........";
String b = ".........._...../.\\/...|.|....\\_/\\........";
void solve() throws IOException{
String x ="";
for(int i=1;i<=6;i++) x = x+bf.readLine();
if(x.compareTo(a)==0)pw.println("m");
else if(x.compareTo(b)==0) pw.println("o");
else pw.println("p");
}
}
}
B
简单博弈。显然必定会消除对方要消除的数，分类讨论即可
import java.io.*;
import java.util.*;
public class Main{
static int maxn = 200005,n,m,inf=0x3fffffff;
static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
static Scanner sc = new Scanner (System.in);
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65536);
static StreamTokenizer st =new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[]args) throws IOException{
new Task().main();
pw.flush();
}
static class Task{
void main() throws IOException {
int T=1;
T=sc.nextInt();
while(T-->0) solve();
}
void solve() throws IOException{
n=sc.nextInt();
int ou=n/2,ji=n-ou;
if(n%2==1) pw.println("Bing");
else if (ou%2==1) pw.println("Bing");
else pw.println("Bong");
}
}
}
C
一种简单的路线是先走到与中央格子的横/纵坐标相同的格子，再前进至中央。复杂度为
import java.io.*;
import java.util.*;
public class Main{
static int maxn = 200005,n,m,inf=0x3fffffff;
static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
static Scanner sc = new Scanner (System.in);
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65536);
static StreamTokenizer st =new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[]args) throws IOException{
new Task().main();
pw.flush();
}
static class Task{
void main() throws IOException {
int T=1;
//T=I();
while(T-->0) solve();
}
void solve() throws IOException{
n=sc.nextInt();
m=sc.nextInt();int k=sc.nextInt();
int x=n/2+1,y=m/2+1;
while(k-->0) {
int a=sc.nextInt(),b=sc.nextInt();
boolean f1=false,f2=false;
if(Math.abs(x-a) >= Math.min(Math.min(x, n-x+1), Math.min(b, m-b+1)))f1=true;
if(Math.abs(y-b) >= Math.min(Math.min(a, n-a+1), Math.min(y, m-y+1)))f2=true;
if(f2&&f1) continue;
ans++;
}
pw.println(ans);
}
}
}
D
容斥。 记录
的阶乘，
记录前导零数当前总数，记录答案时减掉即可
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main{
static int maxn = 200005,n,m,inf=0x3fffffff;
static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
static Scanner sc = new Scanner (System.in);
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65536);
static StreamTokenizer st =new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[]args) throws IOException{
new Task().main();
pw.flush();
}
static final int I() throws IOException {
st.nextToken();
return (int)st.nval;
}
static String S() throws IOException{
String res = bf.readLine();
while(res.equals(""))res=bf.readLine();
return res;
}
static class Task{
void main() throws IOException {
int T=1;
//T=I();
while(T-->0) solve();
}
char[]s;
long fac[] = new long[maxn];
void solve() throws IOException{
n=I();
s = ("*"+S()).toCharArray();
long sum0 = 0;
for(int i=0;i<=n;i++) {
if(i==0) fac[i]=1;
else fac[i] = fac[i-1]*2%mod;
}
for(int i=1;i<=n;i++) {
sum0 = sum0*2%mod;
if(s[i-1]=='0') sum0++;
if((s[i]-'0')%2==1) continue;
ans = (ans + fac[i-1])%mod;
ans = (ans - sum0 + mod)%mod;
}
pw.println(ans);
}
}
}
E
维护一个 的二维数组表示每个字符的下一个位置在哪，然后从
的每一个位置出发得到含
且无
的串，将串能到达最右边的位置记录到答案中。
才知道叫序列自动机
复杂度
import java.io.*;
import java.util.*;
public class Main{
static int maxn = 200005,n,m,inf=0x3fffffff;
static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
static Scanner sc = new Scanner (System.in);
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65536);
static StreamTokenizer st =new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[]args) throws IOException{
new Task().main();
pw.flush();
}
static final int I() throws IOException {
st.nextToken();
return (int)st.nval;
}
static String S() throws IOException{
String res = bf.readLine();
while(res.equals(""))res=bf.readLine();
return res;
}
static class Task{
void main() throws IOException {
int T=1;
//T=I();
while(T-->0) solve();
}
char[]s;
int [][]dp = new int [maxn][26];
char[]arr= "ACCEPT".toCharArray();
void solve() throws IOException{
n=I();m=I();
s = (")"+S()).toCharArray();
for(int i=n;i>=0;i--) {
if(i==n) Arrays.fill(dp[i], n+1);
else {
dp[i]= Arrays.copyOf(dp[i+1], 26);
dp[i][s[i+1]-'A']=i+1;
}
}
for(int i=0;i+m<=n;i++) {
if(s[i+1]=='W') continue;
int l=i+1,r=1+i;
int wl=n+1,ar=-1;//串最左w，最右a
int p=i;
wl=dp[p]['W'-'A'];
for(int j=0;j<6;j++) {
p = dp[p][arr[j]-'A'];
if(p>n) break;
r=p;
}
if(p>n) continue;
p=i;
for(int j=0;j<5;j++) {
int x = dp[p][0];
if(x>r) break;
ar = x;
p=dp[p][arr[j]-'A'];
}
if(wl<ar && ar<r) continue;
ar = Math.min(n,wl<n?dp[wl][0]-1:n);
if(r-l+1<m) r = m+l-1;
ans += Math.max(0, ar-r+1);
}
pw.println(ans);
}
}
}
F
都说典，但我真看半天。。
考虑逐位两点贡献。设 、
为之前一个数此位为
或
且包含这个数的所有区间之和，每次累加计算答案即可。
复杂度
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main{
static int maxn = 200005,n,m,inf=0x3fffffff;
static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
static Scanner sc = new Scanner (System.in);
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65536);
static StreamTokenizer st =new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[]args) throws IOException{
new Task().main();
pw.flush();
}
static final int I() throws IOException {
st.nextToken();
return (int)st.nval;
}
static String S() throws IOException{
String res = bf.readLine();
while(res.equals(""))res=bf.readLine();
return res;
}
static class Task{
void main() throws IOException {
int T=1;
//T=I();
while(T-->0) solve();
}
boolean[][]a = new boolean[maxn][20];
void solve() throws IOException{
n=I();
for(int i=1;i<=n;i++) {
int x=I();
Arrays.fill(a[i], false);
for(int j=19;j>=0;j--) {
if(x<1<<j) continue;
a[i][j]=true;
x-=1<<j;
}
}
for(int j=0;j<=19;j++){
long sum0=0,sum1=0,val=1<<j;
for(int i=1;i<=n;i++){
if(a[i][j]) ans = (ans + sum0*(n-i+1)%mod*val%mod)%mod;
else ans = (ans + sum1*(n-i+1)%mod*val%mod)%mod;
if(a[i][j]) sum1 += i;
else sum0+=i;
}
}
pw.println(ans*2%mod);
}
}
}
G
倍增+哈希
思路挺简单粗暴的，就是维护树根向下的哈希和叶节点向上的哈希，分类讨论即可。复杂度
严谨做法是轻重链剖分+后缀数组， 但是不会
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static Scanner sc = new Scanner(System.in);
static int n,m,maxn=200005,inf = 0x3f3f3f3f;
static long ans=0,mod=(int)1e9+7,INF=(long)2e18;
public static void main(String[]args) throws IOException{
new Task().main();
pw.flush();
}
static int I() throws IOException {
st.nextToken();
return (int)st.nval;
}
static String S() throws IOException {
String res=bf.readLine();
while(res.equals("")) res = bf.readLine();
return res;
}
static class Task{
void main()throws IOException{
int t=1;
//t=I();
while(t-->0) solve();
}
Vector<Vector<Integer>> g = new Vector<>();
char[]s;
long base=2333;
int []dep = new int[maxn>>1];
long []hs = new long[maxn>>1];//自根向下遍历的hash值
int [][]dp = new int[maxn>>1][20];//倍增
long [][]hash = new long[maxn>>1][20];//自下向上的hash值
long []fac = new long[1<<20];
private void solve() throws IOException {
n=I();
for(int i=0;i<=n;i++) g.add(new Vector<>());
for(int i=0;i<1<<20;i++) {
if(i==0) fac[i]=1;
else fac[i] = fac[i-1]*base%mod;
}
s = ("0"+S()).toCharArray();
s[0]=0;
for(int i=1;i<=n;i++) {
int fa=I();
if(i==1) continue;
g.get(fa).add(i);
}
dfs1(1,0,s[0]);
int q = I();
while(q-->0) {
int u=I(),v=I();
int lca = dfs2(u,v);
int len = dep[u]+dep[v]-dep[lca]*2+1;//链长
long l=0,r=0;//两链hash
long left = dep[u]-dep[lca]+1;//u->lca的节点数量
int uu=u,vv=v;//u--uu,vv--v,两段链
int siz = len/2 + (len%2==1?1:0);
if(left >= siz+1) {
uu = get_fa(u,siz-1);
vv = len%2==1?uu:dp[uu][0];
l = (hs[u]-hs[dp[uu][0]]*fac[siz]%mod+mod)%mod;
int len2=dep[vv]-dep[lca]+1,len3=siz-len2;
r = (get_fa_hash(vv,len2-1)*fac[len3]%mod + hs[v]-hs[lca]*fac[len3]%mod+mod)%mod;
}
else {
vv = get_fa(v,siz-1);
uu = len%2==1?vv:dp[vv][0];
r = (hs[v]-hs[dp[vv][0]]*fac[siz]%mod+mod)%mod;
int len2=dep[uu]-dep[lca]+1,len3=siz-len2;
l = (get_fa_hash(uu,len2-1)*fac[len3]%mod + hs[u]-hs[lca]*fac[len3]%mod+mod)%mod;
}
pw.println(l==r ? "YES" : "NO");
}
}
private long get_fa_hash(int v, int t) {//v到v向上第t个点的hash
// TODO Auto-generated method stub
long res=s[v];
for(int j=0;j<20 && t>0;j++,t>>=1) {
if(t%2==1) {
//pw.println("j:"+j);
res = (res*fac[1<<j]%mod + hash[v][j] - s[v]*fac[1<<j]%mod+mod)%mod;
v = dp[v][j];
}
}
return res;
}
private int get_fa(int v, int t) {
// TODO Auto-generated method stub
for(int j=0;j<20 && t>0;j++,t>>=1) {
if(t%2==1) v = dp[v][j];
}
return v;
}
private int dfs2(int u, int v) {
// TODO Auto-generated method stub
if(dep[u]>dep[v]) {
int t=u;u=v;v=t;
}
int t = dep[v]-dep[u];
for(int j=0;j<20 && t>0;j++,t>>=1) {
if(t%2==1) v = dp[v][j];
}
if(u==v) return u;
for(int j=19;j>=0;j--) {
if(dp[u][j] != dp[v][j]) {
u = dp[u][j];v = dp[v][j];
}
}
return dp[u][0];
}
private void dfs1(int i, int fa, long val) {//当前结点，父节点，hash前缀和
// TODO Auto-generated method stub
dep[i] = dep[fa]+1;
hs[i] = (val*base+s[i])%mod;
dp[i][0] = fa;
hash[i][0] = s[i]*base + s[fa];
for(int j=1;j<20;j++) {
dp[i][j] = dp[dp[i][j-1]][j-1];
hash[i][j] = (hash[i][j-1]*fac[(1<<j-1)]%mod + hash[dp[i][j-1]][j-1] - s[dp[i][j-1]]*fac[(1<<j-1)]%mod+mod)%mod;
}
for(int x:g.get(i)) {
if(dep[x]==0) dfs1(x,i,hs[i]);
}
}
}
}
查看21道真题和解析
