牛客小白月赛99
材料打印
https://ac.nowcoder.com/acm/contest/88455/A
A 材料打印
签到。
import java.util.*;
public class Main {
static Scanner sc = new Scanner (System.in);
public static void main(String[]args) {
int t = 1;
t = sc.nextInt();
while(t-->0) solve();
}
static void solve() {
long a=sc.nextInt(),b=sc.nextInt(),x=sc.nextInt(),y=sc.nextInt();
System.out.println(b*y + a*Math.min(x, y));
}
}
B %%%
贪心。每次 mod (n/2+1) 即可；也可打表推出。
import java.util.*;
public class Main {
static Scanner sc = new Scanner (System.in);
public static void main(String[]args) {
int t = 1;
t = sc.nextInt();
while(t-->0) solve();
}
static void solve() {
long n = sc.nextLong();
int cnt = 0;
while(n!=0){
cnt++;
n = n%(n/2+1);
}
System.out.println(cnt);
}
}
打表得到规律，再二分：
import java.util.*;
public class Main {
static Scanner sc = new Scanner (System.in);
public static void main(String[]args) {
int t = 1;
t = sc.nextInt();
while(t-->0) solve();
}
static void solve() {
long n = sc.nextLong();
int l=1,r=63;
long ans = 0;
if(n==0) {
System.out.println(0);return;
}
while(l<=r) {
int mid= (l+r)/2;
if(Math.pow(2, mid+1) - 2 >= n) {
ans = mid;
r=mid-1;
}
else l=mid+1;
}
System.out.println(ans);
}
}
C 迷宫
细节题。
先从终点进行一次搜索，记录每行每列终点可达的最大、最小的位置；再从起点进行一次搜索，判断当前行/列以及旁边两行/列是否清除障碍物后可以到达终点。
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 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 class Task{
void main()throws IOException{
int t=1;
//t=sc.nextI();
while(t-->0) {
solve();
}
}
char[][]g;
int si,sj,ei,ej;
boolean [][][]f = new boolean[2][1002][1002];
int []x = {0,0,1,-1}, y = {1,-1,0,0};
int mi[][] = new int [1002][2];
int mj[][] = new int [1002][2];
boolean v = false;
void solve() throws IOException{
n = sc.nextI();m=sc.nextI();
g = new char[1002][];
for(int i=1;i<=n;i++) {
g[i] = ("#"+sc.next()).toCharArray();
for(int j=1;j<=m;j++) {
if(g[i][j] == 'S') {
si = i;sj = j;
}
if(g[i][j] == 'E') {
ei = i;
ej = j;
}
}
}
for(int i=0;i<=n+1;i++) {
mi[i][0] = inf;
}
for(int j=0;j<=m+1;j++) mj[j][0] = inf;
dfs(ei,ej,1);
dfs(si,sj,0);
if(f[0][ei][ej] || v) {
pw.println("YES");return;
}
pw.println("NO");
}
private void dfs(int i, int j,int p) {
// TODO Auto-generated method stub
if(v) return;
f[p][i][j] = true;
if(p==0) {
if(mi[i][0] < j || mi[i-1][0]<j || mi[i+1][0] < j) {
v=true;return;
}
if(mi[i][1] > j || mi[i-1][1]>j || mi[i+1][1] > j) {
v=true;return;
}
if(mj[j][0] < i || mj[j-1][0] < i || mj[j+1][0] < i) {
v=true;return;
}
if(mj[j][1] > i || mj[j-1][1] > i || mj[j+1][1] > i) {
v=true;return;
}
}
for(int k=0;k<4;k++) {
int xx = i+x[k],yy = j+y[k];
if(xx<=0 || xx>n || yy<1 || yy>m || f[p][xx][yy] || g[xx][yy] == '#') continue;
dfs(xx,yy,p);
}
if(p==1) {
mi[i][0] = Math.min(mi[i][0], j);
mi[i][1] = Math.max(mi[i][1], j);
mj[j][0] = Math.min(mj[j][0], i);
mj[j][1] = Math.max(mj[j][1], i);
}
}
}
static class Input {
Input(InputStream in) { this.in = in; } InputStream in;
byte[] bb = new byte[1 << 15]; int i, n;
byte getc() {
if (i == n) {
i = n = 0;
try { n = in.read(bb); } catch (IOException e) {}
}
return i < n ? bb[i++] : 0;
}
int nextI() {
byte c = 0; while (c <= ' ') c = getc();
int f=1;
int a = 0; while (c > ' ') { if(c=='-') {f=-1;c = getc();continue;}a = a * 10 + c - '0'; c = getc(); }
return a*f;
}
long nextL() {
byte c = 0; while (c <= ' ') c = getc();
int f=1;
long a = 0; while (c > ' ') { if(c=='-') {f=-1;c = getc();continue;}a = a * 10 + c - '0'; c = getc(); }
return a*f;
}
byte[] cc = new byte[1 << 7];
String next() {
byte c = 0; while (c <= ' ') c = getc();
int k = 0;
while (c > ' ') {
if (k == cc.length) cc = Arrays.copyOf(cc, cc.length << 1);
cc[k++] = c; c = getc();
}
return new String(cc, 0, k);
}
}
static Input sc = new Input(System.in);
static String S() throws IOException {
String res=bf.readLine();
while(res.equals("")) res = bf.readLine();
return res;
}
}
D 又是一年毕业季
打表或手推可知答案为为出现过的最小质数（若不为质数，显然其因数也可满足）
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 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 class Task{
void main()throws IOException{
int t=1;
pre();
t=sc.nextI();
while(t-->0) {
solve();
}
}
int []p = new int [maxn];
boolean []f = new boolean[3000000];
void pre() {
int len=0;
for(int i=2;len+1<maxn;i++) {
if(!f[i]) {
p[++len] = i;
for(int j = i+i;j<3000000;j+=i) f[j] = true;
}
}
}
void solve() throws IOException{
n = sc.nextI();
Set<Integer> a = new HashSet<>();
for(int i=0;i<n;i++) a.add(sc.nextI());
for(int i=1;;i++) {
if(!a.contains(p[i])) {
pw.println(p[i]);return;
}
}
}
}
static class Input {
Input(InputStream in) { this.in = in; } InputStream in;
byte[] bb = new byte[1 << 15]; int i, n;
byte getc() {
if (i == n) {
i = n = 0;
try { n = in.read(bb); } catch (IOException e) {}
}
return i < n ? bb[i++] : 0;
}
int nextI() {
byte c = 0; while (c <= ' ') c = getc();
int f=1;
int a = 0; while (c > ' ') { if(c=='-') {f=-1;c = getc();continue;}a = a * 10 + c - '0'; c = getc(); }
return a*f;
}
long nextL() {
byte c = 0; while (c <= ' ') c = getc();
int f=1;
long a = 0; while (c > ' ') { if(c=='-') {f=-1;c = getc();continue;}a = a * 10 + c - '0'; c = getc(); }
return a*f;
}
byte[] cc = new byte[1 << 7];
String next() {
byte c = 0; while (c <= ' ') c = getc();
int k = 0;
while (c > ' ') {
if (k == cc.length) cc = Arrays.copyOf(cc, cc.length << 1);
cc[k++] = c; c = getc();
}
return new String(cc, 0, k);
}
}
static Input sc = new Input(System.in);
static String S() throws IOException {
String res=bf.readLine();
while(res.equals("")) res = bf.readLine();
return res;
}
}
E 多米诺骨牌
sortings。
先按位置排序，将其分为几段连续序列，满足推倒任意序列的第一个骨牌可一直倒塌至该序列最后一骨牌。最后贪心地取即可。
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 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 class Task{
void main()throws IOException{
int t=1;
t=sc.nextI();
while(t-->0) {
solve();
}
}
Vector<int[]> a = new Vector<>();
Vector<Integer> b = new Vector<>();
void solve() throws IOException{
n=sc.nextI();
m=sc.nextI();
a.clear();b.clear();ans=0;
for(int i=1;i<=n;i++) a.add(new int[] {0,sc.nextI()});
for(int i=0;i<n;i++) a.get(i)[0] = sc.nextI();
Collections.sort(a,(o1,o2)->o1[0]-o2[0]);
for(int i=1,j=a.get(0)[0]+a.get(0)[1],k=1;i<n;i++) {
int []o = a.get(i);
if(o[0] > j) {
b.add(k);k=1;
j = o[0]+o[1];
if(i==n-1) {
b.add(k);
}
continue;
}
j = Math.max(j, o[0]+o[1]);
k++;
if(i==n-1) {
b.add(k);
}
}
if(n==1&&m>0) {
pw.println(1);return;
}
Collections.sort(b,(o1,o2)->o2-o1);
for(int i=0,j=m;i<b.size() && j>0;i++,j--) {
ans += b.get(i);
}
pw.println(ans);
}
}
static class Input {
Input(InputStream in) { this.in = in; } InputStream in;
byte[] bb = new byte[1 << 15]; int i, n;
byte getc() {
if (i == n) {
i = n = 0;
try { n = in.read(bb); } catch (IOException e) {}
}
return i < n ? bb[i++] : 0;
}
int nextI() {
byte c = 0; while (c <= ' ') c = getc();
int f=1;
int a = 0; while (c > ' ') { if(c=='-') {f=-1;c = getc();continue;}a = a * 10 + c - '0'; c = getc(); }
return a*f;
}
long nextL() {
byte c = 0; while (c <= ' ') c = getc();
int f=1;
long a = 0; while (c > ' ') { if(c=='-') {f=-1;c = getc();continue;}a = a * 10 + c - '0'; c = getc(); }
return a*f;
}
byte[] cc = new byte[1 << 7];
String next() {
byte c = 0; while (c <= ' ') c = getc();
int k = 0;
while (c > ' ') {
if (k == cc.length) cc = Arrays.copyOf(cc, cc.length << 1);
cc[k++] = c; c = getc();
}
return new String(cc, 0, k);
}
}
static Input sc = new Input(System.in);
static String S() throws IOException {
String res=bf.readLine();
while(res.equals("")) res = bf.readLine();
return res;
}
}
F 自爆机器人
背包。
将每相邻的可操作的墙的距离看作物品体积，最大起爆时间 t 看作容量。显然必定经过n，则转化为容量为 (t-n) 的完全背包；且由于 n<=2e5, 相邻墙之间不同的距离最多有 种，时间复杂度为
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 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 class Task{
void main()throws IOException{
int t=1;
t=sc.nextI();
while(t-->0) {
solve();
}
}
Set<Integer> set = new HashSet<>();
Vector<Integer> a = new Vector<>();
void solve() throws IOException{
n=sc.nextI();
m=sc.nextI();
set.clear();a.clear();
int t=sc.nextI();
while(m-->0) a.add(sc.nextI());
Collections.sort(a);
for(int i=1;i<a.size();i++) set.add(a.get(i)-a.get(i-1));
if(t<n) {
pw.println(0);return;
}
int nn = (t-n)/2;
boolean f[] = new boolean[nn+3];
f[0] = true;
ans=0;
for(int x:set) {
for(int i=0;i+x<=nn;i++) {
f[i+x] |= f[i];
if(f[i+x]) ans = Math.max(ans, i+x);
}
}
pw.println(n+ans*2);
}
}
static class Input {
Input(InputStream in) { this.in = in; } InputStream in;
byte[] bb = new byte[1 << 15]; int i, n;
byte getc() {
if (i == n) {
i = n = 0;
try { n = in.read(bb); } catch (IOException e) {}
}
return i < n ? bb[i++] : 0;
}
int nextI() {
byte c = 0; while (c <= ' ') c = getc();
int f=1;
int a = 0; while (c > ' ') { if(c=='-') {f=-1;c = getc();continue;}a = a * 10 + c - '0'; c = getc(); }
return a*f;
}
long nextL() {
byte c = 0; while (c <= ' ') c = getc();
int f=1;
long a = 0; while (c > ' ') { if(c=='-') {f=-1;c = getc();continue;}a = a * 10 + c - '0'; c = getc(); }
return a*f;
}
byte[] cc = new byte[1 << 7];
String next() {
byte c = 0; while (c <= ' ') c = getc();
int k = 0;
while (c > ' ') {
if (k == cc.length) cc = Arrays.copyOf(cc, cc.length << 1);
cc[k++] = c; c = getc();
}
return new String(cc, 0, k);
}
}
static Input sc = new Input(System.in);
static String S() throws IOException {
String res=bf.readLine();
while(res.equals("")) res = bf.readLine();
return res;
}
}
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 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 class Task{
void main()throws IOException{
int t=1;
t=sc.nextI();
while(t-->0) {
solve();
}
}
Map<Integer,Integer> mp = new HashMap<>();
Vector<Integer> b = new Vector<>();
Vector<int[]> a = new Vector<>();
long []mx = new long[maxn<<2];
long []mi = new long[maxn<<2];
long []k = new long[maxn<<2];
int siz = 0;
void solve() throws IOException{
n = sc.nextI();
m = sc.nextI();
mp.clear();b.clear();a.clear();
for(int i=0;i<n;i++) {
int l=sc.nextI(),r=sc.nextI()-1,y=sc.nextI();
a.add(new int [] {l,r,y});
if(!mp.containsKey(l)) {
mp.put(l,0);b.add(l);
}
if(!mp.containsKey(r)) {
mp.put(r,0);b.add(r);
}
}
Collections.sort(b);
for(int i=0;i<b.size();i++) {
mp.put(b.get(i), i+1);
}
for(int i=0;i<n;i++) {
int l=a.get(i)[0],r=a.get(i)[1];
a.get(i)[0] = mp.get(l);
a.get(i)[1] = mp.get(r);
}
Collections.sort(a,(o1,o2)->o1[2]-o2[2]);
siz = mp.size();
for(int i=1;i<=siz<<2;i++) {
mx[i] = mi[i] = m;
k[i] = 0;
}
for(int []o : a) {
int l = o[0],r = o[1],y = o[2];
modify(1,1,siz,l,r,y);
}
pw.println(mx[1]);
}
private void modify(int i, int l, int r, int ll, int rr, int y) {
// TODO Auto-generated method stub
if(ll<=l && r<=rr) {
if(mi[i] >= y) {
mi[i] += y;mx[i] += y;
k[i] += y;return;
}
if(mx[i] < y) return;
pd(i,l,r);
int mid=l+r>>1;
modify(i<<1,l,mid,ll,rr,y);
modify(i<<1|1,mid+1,r,ll,rr,y);
up(i);
return;
}
pd(i,l,r);
int mid=l+r>>1;
if(mid>=ll) modify(i<<1,l,mid,ll,rr,y);
if(mid+1<=rr) modify(i<<1|1,mid+1,r,ll,rr,y);
up(i);
}
private void pd(int i,int l,int r) {
// TODO Auto-generated method stub
if(k[i] > 0) {
k[i<<1] += k[i];k[i<<1|1] += k[i];
mx[i<<1] += k[i];mi[i<<1] += k[i];
mx[i<<1|1] += k[i];mi[i<<1|1] += k[i];
k[i] = 0;
}
}
void up(int i) {
mx[i] = Math.max(mx[i<<1], mx[i<<1|1]);
mi[i] = Math.min(mi[i<<1], mi[i<<1|1]);
}
}
static class Input {
Input(InputStream in) { this.in = in; } InputStream in;
byte[] bb = new byte[1 << 15]; int i, n;
byte getc() {
if (i == n) {
i = n = 0;
try { n = in.read(bb); } catch (IOException e) {}
}
return i < n ? bb[i++] : 0;
}
int nextI() {
byte c = 0; while (c <= ' ') c = getc();
int f=1;
int a = 0; while (c > ' ') { if(c=='-') {f=-1;c = getc();continue;}a = a * 10 + c - '0'; c = getc(); }
return a*f;
}
long nextL() {
byte c = 0; while (c <= ' ') c = getc();
int f=1;
long a = 0; while (c > ' ') { if(c=='-') {f=-1;c = getc();continue;}a = a * 10 + c - '0'; c = getc(); }
return a*f;
}
byte[] cc = new byte[1 << 7];
String next() {
byte c = 0; while (c <= ' ') c = getc();
int k = 0;
while (c > ' ') {
if (k == cc.length) cc = Arrays.copyOf(cc, cc.length << 1);
cc[k++] = c; c = getc();
}
return new String(cc, 0, k);
}
}
static Input sc = new Input(System.in);
static String S() throws IOException {
String res=bf.readLine();
while(res.equals("")) res = bf.readLine();
return res;
}
}
