刷题记录

常见题型

• 模拟
• STL
• 字符串
• 数字
• 暴力
• 搜索（BFS/DFS）
• 图论
• 贪心
• DP

PIPIOJ周赛记录

PAT记录

常用技巧

• 多组输入

  // c++使用方法
  while(cin>>c && c != 0){
  	...
  }
  
  // c使用方法
  while(scanf("%d", &t) != EOF){
      ...
  }
             

• 直接输入，输出16进制

  scanf("%llx", &a);
  printf("%llx", a);
             

• 结构体使用地址尽量使用指针，不然可能会出现以下问题

  struct Node{
  	int id;
  };
  
  void test1(){
  	Node *t;
  	for(int i = 0; i < 2; i ++){
  		Node *node = (Node*)malloc(sizeof(Node));
  		node->id = i;
  		if(i == 0){
  			t = node;
  		}
  		cout<<"i:"<<i<<endl;
  		printf("%p\n", node);//新分配的地址
  	}
  	
  	cout<<t->id<<endl;//为0
  	return 0;
  }
  
  void test2(){
  	Node *t;
  	for(int i = 0; i < 2; i ++){
  		Node node;
  		node.id = i;
  		if(i == 0){
  			t = &node;
  		}
  		cout<<"i:"<<i<<endl;
  		printf("%p\n", &node);//每次都一样，同一个地址
  	}
  	
  	cout<<t->id<<endl;//为1
  	return 0;
  }
             

• 字符串输入输出

  //c++使用头文件<bits/stdc++.h>
  string s;
  printf("%s", s.c_str());//string不是c中的string，需要调用c_str()才能对应%s
  
  //输入一行
  getline(cin, s);//输入一行，包括空格，直到换行符为止
  gets(s);//输入一行，包括空格，直到换行符为止
             

• 字符数组定义

  char str[10] = {"0123456789"};
             

• ctype头文件使用

  #include<ctype>
  bool isDigial(char c);//判断是否是数据
  char tolower(char c);//转换成小写
             

• 对于特定格式的输入可以使用scanf();简化

  //输入 "11:12"
  scanf("%d:%d", &a, &b);//简化了':'处理
  
  //对于单个字符前的无效空格和换行
  scanf(" %c", c);//自动跳过之前的无效空格与换行
             

常见错误

• 判断数据类型以及数据范围
  • 何时使用int和double
  • 是否需要使用long long

  //long long的输入与输出
    long long a;
    printf("%lld", a);//或printf("%l64", a);
    
    //强转long long
    long long c = 1ll * a * b;