头像

Bonker

中国计量大学




离线:12小时前


最近来访(41)
用户头像
瓜田
用户头像
张栋
用户头像
我是sun
用户头像
Kiribati
用户头像
Pipipapi
用户头像
CyTime
用户头像
zxt
用户头像
Lighthouse_3
用户头像
TheBlaze
用户头像
yxc
用户头像
向郭子源同学学习
用户头像
zombotany
用户头像
亦ssue
用户头像
写bug大师


Bonker
12小时前

//题目没搞懂时,是想用stack的或直接输出进行匹配,但是,这道题的意思是真的难搞懂
//题解的思路也是清奇,是真的牛

例子:[(])-->[]([])
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int a[110]; // 标记
int main()
{
    int i,j;
    string s;
    cin >> s;
    for (i=0; i<s.length(); i++) {
        if (s[i] == ')') { // 找到了右括号
            for (j=i-1; j>=0; j--) {
                if (s[j] == '(' and a[j] == 0) { // 找到了没被匹配过的左括号且匹配成功,这里就可构成规则序列了
                    a[i] = a[j] = 1;//标记匹配成功的,然后可以用规则序列了,直接就是包括
                    break;
                }
                else if (s[j] == '[' and a[j] == 0) break; // 找到了左括号但匹配失败,就是相当于不构成规则序列
            }
            // 找不到左括号,不做任何操作
        }
        // 下面同理
        else if (s[i] == ']') {
            for (j=i-1; j>=0; j--) {
                if (s[j] == '[' and a[j] == 0) {
                    a[i] = a[j] = 1;
                    break;
                }
                else if (s[j] == '(' and a[j] == 0) break;
            }
        }
    }
    for (i=0; i<s.length(); i++) {
        if (a[i] == 0) { // 没有匹配则成对输出
            if (s[i] == '(' or s[i] == ')') cout << "()";//直接就是两个字符代替一个字符
            else cout << "[]";
        }
        else cout << s[i]; // 匹配成功则直接输出
    }
    return 0;
}



Bonker
12小时前

//按人头来索引,用时间来分类,思路性太强了

#include<iostream>
using namespace std;
int s,i,n,t,k,r,w[100010],x[300010],y[300010];
int main(){
    cin>>n;
    while(n--){//这里是读入的操作
        cin>>t>>k;
        while(k--){
            y[++r]=t;cin>>x[r];//读入人的国籍,人也附上时间,也就是说用时间来索引人
            if(!w[x[r]])s++;//如果当前放入人的国籍没有出现过s就加一
            w[x[r]]++;//当前船上人的国籍加一
        }
        while(t-y[i]>=86400)//i从零开始,犹如队列一般
            if(!--w[x[i++]])s--;//这里是遍历每个人,如果这个国籍的人减完了,s就--
        cout<<s<<endl;
    }
}



Bonker
22小时前

分享链接:https://www.cnblogs.com/fat39/p/7159881.html

PI = 3.141592653
print('%10.3f'%PI)  #字段宽10,精度3
#     3.142

#精度为3,所以只显示142,指定宽度为10,所以在左边需要补充5个空格,以达到10位的宽度
PI=3.1415926
print("PI=%.*f"%(3,PI))
#用*从后面的元组中读取字段宽度或精度,可以读取出来精度是3位
#PI=3.142 

#没有指定宽度,所以不需要缩进

print("PI=%*.3f"%(10,PI))   #精度为3,总长为10.
# PI=     3.142

#* 所处的位置不同,读取的内容也不同

//写法注意

print("%d  %d" %(a,b))



Bonker
1天前

//stl的list用法的典型题目

#include <cstdio>
#include <list>
using namespace std;
const int maxN = 1e5 + 10;
list<int>::iterator pos[maxN];
list<int> queList;
bool erased[maxN];
int N;
void buildQueue()
{
  queList.push_front(1);
  pos[1] = queList.begin();
  for (int i = 2; i <= N; i++)
  {
      int k, p;
      scanf("%d%d", &k, &p);
      if (p == 0)
      {
          pos[i] = queList.insert(pos[k], i); //left
      }
      else
      {
          auto nextIter = next(pos[k]);//向当前元素的前面添加元素
          pos[i] = queList.insert(nextIter, i); //right
      }
  }
  int M;
  scanf("%d", &M);
  for (int x, i = 1; i <= M; i++)
  {
      scanf("%d", &x);
      if (!erased[x])
      {
          queList.erase(pos[x]);
      }
      erased[x] = true;
  }
}
int main()
{
  scanf("%d", &N);
  buildQueue();
  bool first = true;
  for (int x: queList)
  {
      if (!first)
          putchar(' ');
      first = false;
      printf("%d", x);
  }
  putchar('\n');
  return 0;
}

//ps:stl的list的学习网站 http://c.biancheng.net/view/6892.html




Bonker
1天前

//朴素版的筛素数 O(nlogn)

void get_primes1(int n) {
    for(int i = 2; i <= n; i++) {//每个i都要处理
        if(!st[i]) prime[cnt++] = i;//false是质数,true是合数
        for(int j = i+i; j <= n; j += i)//倍增法,加i的加,每个数都是
            st[j] = true;
    }
}

//埃式筛法 O(nloglogn)

void get_primes2(int n) {
    for(int i = 2; i <= n; i++) {//每个i都要处理
        if(!st[i]){ 
            prime[cnt++] = i;
            for(int j = i; j <= n; j += i)//在质数的前提下,筛选合数
                st[j] = true;
        }
    } 
}

//线性筛法 O(n)

void get_prime(int n) {
    for(int i = 2; i <= n; i++) {
        if(!st[i]) prime[cnt++] = i;//都是质数
        for(int j = 0; prime[j] <= n / i; j++) {//也就是小于sqrt,i从0开始计数
            //对于任意一个合数x,假设pj为x最小质因子,当i<x/pj时,一定会被筛掉
            st[prime[j]*i] = true;//倍数
            if(i % prime[j] == 0) break;//继续扩大,说明i是prime[j]的倍数了,找下个质数进行倍增,i%pj == 0, pj定为i最小质因子,pj也定为pj*i最小质因子
            /*
            1.i%pj == 0, pj定为i最小质因子,pj也定为pj*i最小质因子
            2.i%pj != 0, pj定小于i的所有质因子,所以pj也为pj*i最小质因子
            */
        }
    }
} 

//比较快的判断素数的方法

bool ispri(int k) {
    if(k <= 1) return false;
    if(k <= 3) return true;
    if(k % 6 != 1 && k % 6 != 5) return false;
    for(int i = 5;i < k / i;i += 6) {
        if(k % i == 0 || k % (i + 2) == 0) return false;
    }
    return true;
}



Bonker
3天前

这里分了两种情况来分析,也就是y总说的只考虑最后的一步,也就是状态转移方程,这里分析的十分牛,ORZ

//分两种情况:第N列是排好的,没有伸到第N-1列;第N列是排好的,有一个排到了第N-1列的位置
//f[n] = f[n-1]+f[n-2]  第一种情况的方案数
//g[n-2] = f[n-3]+ g[n-3]  第二种情况的方案数
//f[N]是记录已经是排满了的方案数
//g[N]是记录有一个伸出来的方案数
#include<iostream>
using namespace std;
const int N = 1e6+10,mod = 10000;
int n;
int f[N];
int g[N];
int main(){
    cin>>n;
    f[0] = 1;//没有方案数
    g[1] = 1;//从一开始
    f[1] = 1;//只有竖着的
    for(int i=2;i<=n;i++)//从一开始的for,dp   nb
    {
        f[i]=((f[i-1]+f[i-2])%mod+2*g[i-2]%mod)%mod;
        g[i]=(g[i-1]+f[i-1])%mod;
    }
    cout<<f[n];
    return 0;
}



Bonker
4天前
import java.util.Scanner;

class Node{
    char val;
    Node left;
    Node right;
    public Node(char val){
        this.val=val;
    }
}
public class Main {
    public static Node buildTree(String str){
        Node node=null;
        if(str.length()==1){
            node=new Node(str.charAt(0));
            return node;
        }
        int p=0,c1=-1,c2=-1;            //p,c1,c2分别存放未匹配的括号数量,最右出现的+-号下标,最右出现的*/号下标
        for(int i=0;i<str.length();i++){
            switch(str.charAt(i)){
            case '(': 
                p++;
                break;
            case ')': 
                p--;
                break;
            case '+': case'-': 
                if(p==0) 
                    c1=i;
                break;
            case '*': case'/':
                if(p==0)
                    c2=i;
                break;
            }
        }
        if(c1<0&&c2<0)          //整个表达式是被一对括号括起来的
            node=buildTree(str.substring(1, str.length()-1));
        else if(c1>0){//+,-的子树
            node=new Node(str.charAt(c1));
            node.left=buildTree(str.substring(0,c1));
            node.right=buildTree(str.substring(c1+1,str.length()));//递归实现树的建立,有点像归并排序的操作
        }else{//*,/的子树
            node=new Node(str.charAt(c2));
            node.left=buildTree(str.substring(0,c2));
            node.right=buildTree(str.substring(c2+1,str.length()));
        }
        return node;
    }
    public static void postOrder(Node node){
        if(node==null)
            return;
        postOrder(node.left);//不断的左边
        postOrder(node.right);//不断的右边
        System.out.print(node.val);//当null返回后直接输出当前的val
    }
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            String str=scanner.nextLine();
            Node root=buildTree(str);
            postOrder(root);
            System.out.println();
        }
        scanner.close();
    }
}

//通过后缀表达式来实现前缀表示式和中缀表达式的转换,这里实现不了有括号的实现

import java.util.Scanner;
import java.util.Stack;

class Node{
    char val;
    Node left;
    Node right;
    public Node(char val){
        this.val=val;
    }
}
public class Main {
    public static Node buildTree(String str){
        Stack<Node> stack=new Stack<Node>();
        for(char c:str.toCharArray()){//string的数据通过toCharArray()方法实现遍历
            if(c=='+'||c=='-'||c=='*'||c=='/'){
                Node node=new Node(c);
                Node right=stack.pop();
                Node left=stack.pop();
                node.left=left;
                node.right=right;
                stack.push(node);
            }else{
                Node node=new Node(c);
                stack.push(node);
            }
        }
        Node root=stack.pop();
        return root;
    }
    public static void preOrder(Node node){//前置表达式
        if(node==null)
            return;
        System.out.print(node.val);
        preOrder(node.left);
        preOrder(node.right);
    }
    public static void inOrder(Node node){//中置表达式
        if(node==null)
            return;
        inOrder(node.left);
        System.out.print(node.val);
        inOrder(node.right);
    }
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            String str=scanner.nextLine();
            Node root=buildTree(str);
            preOrder(root);//从子节点开始
            System.out.println();
            inOrder(root);
            System.out.println();
        }
        scanner.close();
    }
}



Bonker
5天前

//这道题的思路十分好,f[1][1]=1,f[2][1]=2;//初始化nb,这里所有的数就是由1和2组成的(这句话真nb),还有高精度的练习,太细了

#include <cstdio>
using namespace std;
int n,m,len=1;
int f[1005][1005];
void plus(int x)
{
    for(int i=1;i<=len;i++)
      f[x][i]=f[x-1][i]+f[x-2][i];
    for(int i=1;i<=len;i++)//步数上的高精度
      if(f[x][i]>9)
      {
        f[x][i+1]+=f[x][i]/10;
        f[x][i]%=10;
      }
    if(f[x][len+1]) len++;//补一
}
int main ()
{
    scanf("%d%d",&m,&n);
    f[1][1]=1,f[2][1]=2;//初始化nb,这里所有的数就是由1和2组成的
    for(int i=3;i<=n-m;i++) plus(i);//步数
    for(int i=len;i;i--) printf("%d",f[n-m][i]);
    return 0;
}



Bonker
7天前

//动态的数组分配的实现

class activeArray {
public:
    activeArray(int size);
    ~activeArray();
    int size;
    int** a = new int* [size];//二维数组的动态实现
};
activeArray::activeArray(int size) {
    this->size = size;
}
activeArray::~activeArray() {
    delete[] a;
}

用main函数来调配

activeArray aa(size);
//下面一句很重要,二维数组的实现关键
aa.a[i] = new int[aa.size];


活动打卡代码 AcWing 1077. 皇宫看守

Bonker
11天前

//有点不太理解了,f[u][1]的情况

//皇宫各个宫殿的分布,呈一棵树的形状,宫殿可视为树中结点,两个宫殿之间如果存在道路直接相连,则该道路视为树中的一条边。
//已知,在一个宫殿镇守的守卫不仅能够观察到本宫殿的状况,还能观察到与该宫殿直接存在道路相连的其他宫殿的状况。
//f[i][0]第i个结点的父结点被选    f[i][1]第i个结点有一个子节点被选     f[i][2]第i个节点本身被选
//f[i][0] = min(f[v][1],f[v][2])
//f[i][1] = min(f[v][2]+sum(min(f[s][1]),f[s][2]))
//f[i][2] += min(f[v][1],f[v][2],f[v][0])
#include <iostream>
#include <cstring>
using namespace std;

/*
以下注释为早期笔记,希望对你有所帮助

状态机 + 树形Dp问题
状态表示:
    f(i, 0):第i号结点被他的父结点安排的守卫看住的方案数
    f(i, 1):第i号结点被他的子结点安排的守卫看住的方案数
    f(i, 2):第i号结点自己安排守卫看住的方案数
状态计算:(j是i的子结点)
    f(i, 0) = sum{min(f(j,1), f(j,2))}
        i是被他父结点看住的,那他的子结点要么自己看自己,要么被自己的子结点看住
    f(i, 1) = min{w(k) + f(k, 2) + sum{min(f(j,1), f(j,2))}}
        i如果是被自己点看住的,那么就要枚举他是被哪个子结点看住的所有方案,对所有方案求最小值
        这里的sum不包括j==k的情况,因此需要手动额外减去
    f(i, 2) = sum{min(f(j,0), f(j,1), f(j,2))} + w(u)
        i是被自己看住的,那他的子结点可以被父结点看住,可以自己看自己,也可以被自己的子结点看住
*/
const int N = 1510;
int n;
int h[N], w[N], e[N], ne[N], idx;
int f[N][3];
bool st[N];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = 1e9; //f[u][1]求最小值,初始化为最大值
    f[u][2] = w[u];//初始化放置自己的代价,自己雇佣自己的费用
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);
        f[u][0] += min(f[j][1], f[j][2]);//不选自己的时候
        f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);//其实这里就是三种情况的取最小,三者之间的比较
    }
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        //f[u][0]中记录了sum{min(f(j,1), f(j,2))},再从中减去对应的贡献即可得到remain ver
        f[u][1] = min(f[u][1], f[u][0] + f[j][2] - min(f[j][1], f[j][2]));//这里是选了子节点???
    }
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int id, cnt, cost;
        cin >> id >> cost >> cnt;
        w[id] = cost;//安置的钱数
        while (cnt--) {
            int ver;
            cin >> ver;
            add(id, ver);//有向图处理
            st[ver] = true;
        }
    }
    int root = 1;
    while (st[root]) ++root;//根除有向图的困扰
    dfs(root);
    printf("%d\n", min(f[root][1], f[root][2]));//子节点的选择还是自己的选择
    return 0;
}