题目链接：https://www.nowcoder.com/acm/contest/74#description
吐槽一下这场比赛其实出的锅好多。。我当场反映了一个数据问题，客服回复说没有问题，然而过一会又通知说确实出现了我说的问题。。。。然后就是输入，并不能理解这个输入方式，一会儿是单组一会儿是多组。
当然自己的心态很爆炸，自己的水平也很菜。
A 吐泡泡
考虑到数据量的问题，加上之前也遇到了奇怪的问题，可以使用一个个往里面加字符的方法进行处理。详情见代码。
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
FastScanner fs = new FastScanner();
while (fs.hasNext()) {
String s = fs.nextToken();
char[] temp = s.toCharArray();
String res = "";
for (int i = 0; i < temp.length; i++) {
res += temp[i];
res = change(res);
}
System.out.println(res);
}
}
public static String change(String s) {
boolean changed = true;
while (s.length() > 1) {
changed = false;
if (s.endsWith("OO")) {
s = s.substring(0, s.length() - 2);
changed = true;
} else if (s.endsWith("oo")) {
s = s.substring(0, s.length() - 2);
s += "O";
changed = true;
}
if (!changed) {
break;
}
}
return s;
}
public static class FastScanner {
private BufferedReader br;
private StringTokenizer st;
// 级别最高
void eat(String s) {
st = new StringTokenizer(s);
}
// 级别第二
public FastScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
eat("");
}
public FastScanner(String s) {
try {
br = new BufferedReader(new FileReader(new File(s)));
eat("");
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
// 级别第三
public String nextLine() {
try {
return br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return null;
}
public boolean hasNext() {
while (!st.hasMoreTokens()) {
String s = nextLine();
if (s == null) {
return false;
}
eat(s);
}
return true;
}
// 级别第四
public String nextToken() {
hasNext();
return st.nextToken();
}
// 级别第五
public int nextInt() {
return Integer.valueOf(nextToken());
}
public long nextLong() {
return Long.valueOf(nextToken());
}
public double nextDoube() {
return Double.valueOf(nextToken());
}
}
}
B TaoTao要吃鸡
找到一份很好的博客：http://blog.csdn.net/nobleman__/article/details/79187856
当时并没有想到这个思路，如果能想到，那么是能写出来的// 但是就是没有人家聪明，就是想不出来
C 小仙女过生日啦
我觉得整个事情非常的不对，因为我怎么记得比赛的时候是要求切出来的最大的蛋糕最大？？？现在题目怎么变成了最大的蛋糕最小？？？
画图发现给出的多边形并不是凸多边形。。。
找了一篇很好的博文：https://www.cnblogs.com/Konjakmoyu/p/4905563.html
然而博文上的代码我并没有改成能通过测试。。。于是另找了一份。
代码来源：https://www.nowcoder.com/acm/contest/view-submission?submissionId=21218063
#include <bits/stdc++.h>
using namespace std;
struct node {
double x, y;
} t[105];
double dp[105][105];
int n;
double T(double x) {
return x < 0 ? -x : x;
}
double mul(node a, node b, node c) {
return T((a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y)) / 2.0;
}
inline bool chk(int a, int b, int c) {
double area = mul(t[a], t[b], t[c]);
for (int i = 1; i <= n; i++) {
if (i == a || i == b || i == c) {
continue;
}
double s1 = mul(t[i], t[a], t[b]), s2 = mul(t[i], t[a], t[c]), s3 = mul(t[i], t[b], t[c]);
if (fabs(s1 + s2 + s3 - area) < 1e-8) {
return 0;
}
}
return 1;
}
int main() {
int i, j, k, d;
while (scanf("%d", &n) != EOF) {
for (i = 1; i <= n; i++) {
scanf("%lf%lf", &t[i].x, &t[i].y);
}
for (d = 3; d <= n; d++) {
for (i = 1; i + d - 1 <= n; i++) {
if (d == 3) {
dp[i][i + 2] = mul(t[i], t[i + 1], t[i + 2]);
continue;
}
j = i + d - 1;
dp[i][j] = 0x3f3f3f3f;
for (k = i + 1; k < j; k++) {
if (chk(i, j, k)) {
dp[i][j] = min(dp[i][j], max(mul(t[i], t[j], t[k]), max(dp[i][k], dp[k][j])));
}
}
}
}
printf("%.1lf\n", dp[1][n]);
}
return 0;
}D YB要打炉石
求非下降子序列的长度。长度大于等于30则符合，否则不符合。
#include<cstdio>
#include<algorithm>
const int MAXN=200001;
int a[MAXN];
int d[MAXN];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
d[1]=a[1];
int len=1;
for(int i=2;i<=n;i++)
{
if(a[i]>=d[len])
d[++len]=a[i];
else
{
int j=std::lower_bound(d+1,d+len+1,a[i])-d;
d[j]=a[i];
}
}
if(len < 30) {
printf("no");
} else {
printf("yes");
}
return 0;
}E 小G有一个大树
这是有关树的中心的题目
原题链接（原题中会给出数据数，此题中没有给出，仅此一处区别）：http://poj.org/problem?id=1655
看到了一篇很好的博客：https://www.cnblogs.com/patrickzhou/p/5867208.html
该代码源自上面的博客中：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int N; // 1<= N <= 20000
const int maxn = 20000;
vector<int> tree[maxn + 5]; // tree[i]表示节点i的相邻节点
int d[maxn + 5]; // d[i]表示以i为根的子树的节点个数
#define INF 10000000
int minNode;
int minBalance;
void dfs(int node, int parent) // node and its parent
{
d[node] = 1; // the node itself
int maxSubTree = 0; // subtree that has the most number of nodes
for (int i = 0; i < tree[node].size(); i++) {
int son = tree[node][i];
if (son != parent) {
dfs(son, node);
d[node] += d[son];
maxSubTree = max(maxSubTree, d[son]);
}
}
maxSubTree = max(maxSubTree, N - d[node]); // "upside substree with (N - d[node]) nodes"
if (maxSubTree < minBalance){
minBalance = maxSubTree;
minNode = node;
} else if(maxSubTree == minBalance && node < minNode) {
minNode = node;
}
}
int main()
{
while (~scanf("%d", &N)){
for (int i = 1; i <= N - 1; i++){
tree[i].clear();
}
for (int i = 1; i <= N-1; i++){
int u, v;
scanf("%d%d", &u, &v);
tree[u].push_back(v);
tree[v].push_back(u);
}
minNode = 0;
minBalance = INF;
dfs(1, 0); // fist node as root
printf("%d %d\n", minNode, minBalance);
}
return 0;
}F 德玛西亚万岁
自己并不是很会状态压缩dp，所以从网上找了一份教程学了一下。
参考链接：http://blog.csdn.net/harrypoirot/article/details/23163485
参考链接：http://blog.csdn.net/accry/article/details/6607703
来自上面参考链接的代码：
#include <cstdio>
#include <cstring>
using namespace std;
#define mod 100000000
int M,N,top = 0;
//top表示每行最多的状态数
int state[600],num[110];
//state存放每行所有的可行状态（即没有相邻的状态
//
int dp[20][600];
//dp[i][j]:对于前i行数据，每行有前j种可能状态时的解
int cur[20];
//cur[i]表示的是第i行整行的情况
inline bool ok(int x){ //判断状态x是否可行
if(x&x<<1) return false;//若存在相邻两个格子都为1，则该状态不可行
return true;
}
void init(){ //遍历所有可能的状态
top = 0;
int total = 1 << N; //遍历状态的上界
for(int i = 0; i < total; ++i){
if(ok(i))state[++top] = i;
}
}
inline bool fit(int x,int k){ //判断状态x 与第k行的实际状态的逆是否有‘重合’
if(x&cur[k])return false; //若有重合，（即x不符合要求）
return true; //若没有，则可行
}
int main(){
while(scanf("%d%d",&M,&N)!= EOF){
init();
memset(dp,0,sizeof(dp));
for(int i = 1; i <= M; ++i){
cur[i] = 0;
int num;
for(int j = 1; j <= N; ++j){ //输入时就要按位来存储，cur[i]表示的是第i行整行的情况，每次改变该数字的二进制表示的一位
scanf("%d",&num); //表示第i行第j列的情况（0或1）
if(num == 0) //若该格为0
cur[i] +=(1<<(N-j)); //则将该位置为1（注意要以相反方式存储，即1表示不可放牧
}
}
for(int i = 1;i <= top;i++){
if(fit(state[i],1)){ //判断所有可能状态与第一行的实际状态的逆是否有重合
dp[1][i] = 1; //若第1行的状态与第i种可行状态吻合，则dp[1][i]记为1
}
}
/* 状态转移过程中，dp[i][k] =Sigma dp[i-1][j] （j为符合条件的所有状态） */
for(int i = 2; i <= M; ++i){ //i索引第2行到第M行
for(int k = 1; k <= top; ++k){ //该循环针对所有可能的状态，找出一组与第i行相符的state[k]
if(!fit(state[k],i))continue; //判断是否符合第i行实际情况
for(int j = 1; j <= top ;++j){ //找到state[k]后，再找一组与第i-1行符合，且与第i行（state[])不冲突的状态state[j]
if(!fit(state[j],i-1))continue; //判断是否符合第i-1行实际情况
if(state[k]&state[j])continue; //判断是否与第i行冲突
dp[i][k] = (dp[i][k] +dp[i-1][j])%mod; //若以上皆可通过，则将'j'累加到‘k'上
}
}
}
int ans = 0;
for(int i = 1; i <= top; ++i){ //累加最后一行所有可能状态的值，即得最终结果！！！泥马写注释累死我了终于写完了！
ans = (ans + dp[M][i])%mod;
}
printf("%d\n",ans);
}
} G 送分了QAQ
记 中不喜欢的个数为 ，则 之间不喜欢的个数为
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[] notLike = new int[1000010];
static int cnt = 0;
public static void main(String[] args) {
FastScanner fs = new FastScanner();
init();
while(true) {
N = fs.nextInt();
M = fs.nextInt();
if(N == 0 && M == 0) {
break;
}
if(N == 0) {
N = 1;
}
System.out.println(notLike[M] - notLike[N-1]);
}
}
public static void init() {
notLike[0] = 0;
for(int i = 1; i < notLike.length; i++) {
String string = String.valueOf(i);
if(string.contains("38") || string.contains("4")) {
cnt++;
notLike[i] = cnt;
} else {
notLike[i] = cnt;
}
}
}
public static class FastScanner {
private BufferedReader br;
private StringTokenizer st;
// 级别最高
void eat(String s) {
st = new StringTokenizer(s);
}
// 级别第二
public FastScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
eat("");
}
public FastScanner(String s) {
try {
br = new BufferedReader(new FileReader(new File(s)));
eat("");
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
// 级别第三
public String nextLine() {
try {
return br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return null;
}
public boolean hasNext() {
while (!st.hasMoreTokens()) {
String s = nextLine();
if (s == null) {
return false;
}
eat(s);
}
return true;
}
// 级别第四
public String nextToken() {
hasNext();
return st.nextToken();
}
// 级别第五
public int nextInt() {
return Integer.valueOf(nextToken());
}
public long nextLong() {
return Long.valueOf(nextToken());
}
public double nextDoube() {
return Double.valueOf(nextToken());
}
}
}
H 了断局
规律：
找出规律之后，想怎么搞怎么搞，我使用的是记忆化。
#include <cstring>
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iomanip>
#include <vector>
using namespace std;
long long a[55];
long long get_res(int n) {
if(a[n] != -1) {
return a[n];
}
return a[n] = get_res(n-1) + get_res(n-2) + get_res(n-3);
}
int main() {
for(int i = 0; i < 55; i++) {
a[i] = -1;
}
a[0] = 0L;
a[1] = 1L;
a[2] = 1;
long long n;
while(cin >> n) {
cout << get_res(n-1) << endl;
}
return 0;
}