这几天做的第二道这种路的类型不一样，分策略进行松弛的最短路题，这道和上一道就是一模一样 给出m条路，有car的walk的，要使walk尽量小的情况下再使总路途最小 核心就是Dijk的队列节点要维护两个权值，然后优先级是walk的优先，然后松弛的时候要分情况 #include <bits/stdc++.h> using namespace std; #define bug printf("BUG\n") const int N=4050; const int M=80050; const int INF=0x3f3f3f3f; struct Edge{  int ...

奇数肯定在第一个里，而偶数就不一定了，要判断这个偶数要除以多少次2才能变成奇数，如果次数是奇数次，比如1次，那肯定是第二个里了，因为第二个放的就是第一个的两倍嘛 #include <bits/stdc++.h> using namespace std; typedef long long ll; int n; ll x; int main(void){  scanf("%d",&n); while(n--){  scanf("%lld",&x); if(x%2){  printf("First Box\n"...

判负环就是看入队次数>n import java.util.Queue; import java.util.Scanner; import java.util.concurrent.LinkedBlockingDeque; public class Main {  static class Edge{  int v,w,next; Edge(int v,int w,int next){  this.v=v; this.w=w; this.next=next; } } static final int N= 100500; static final int M=1000050; stati...

Java里没有c++的lower_bound和upper_boud，要自己写 import java.util.Arrays; import java.util.Queue; import java.util.Scanner; import java.util.concurrent.LinkedBlockingDeque; public class Main {  /** * 二分查找 当v在nums中出现时返回出现的第一个位置，否则返回一个idx，在这里插入v时nums仍有序 * @param nums 非降序数组 * @param l * @param r * @param v * @re...

Java里也没有这个东西… public class Main{  /** * 下一个排列 stl中的next_permutation() * @param nums * @return */ static boolean nextPermutation(int[] nums){  //将数组分为三部分，第二部分是一个元素，第三部分是递减子序列 int len=nums.length; for(int i=len-1;i>0;i--){  //找到第二第三部分的分界线 if(nums[i]>nums[i-1]){  //v即为第二部分元素 int v=nums[i-1]; int ...

多源最短路floyd import java.util.Scanner; public class Main{  static int m,n,u,v,w; static final int N=150; static final int INF=0x3f3f3f3f; static long[][] g=new long[N][N]; static void floyd(){  for(int k=1;k<=n;k++){  for(int i=1;i<=n;i++){  for(int j=1;j<=n;j++){  if(g[i][j]>g[i][k]+g[k][...

用处应该不大因为蓝桥杯应该用不到这个 主要写了一道floyd c++ 7ms java 1500ms … 用了这个模板读入之后是1000ms左右 import java.io.*; import java.util.StringTokenizer; public class Main{  static class InputReader{  public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) {  reader = new BufferedR...

坑爹的签到题，差点做不出来 给一个数组，求其中两个数相加为完全平方数的对数 n是1e5 暴力会超时的，所以先预处理出2*1e5内的完全平方数，然后每输入一个数，就标记下它需要和哪个数相加才能凑成完全平方数，然后后面的每读入一个除了要记录，还要看这个数是否前面已经被记录过，就是加上它就能凑成完全平方数，直接加上num[a[i]]，然后还要开long long #include <bits/stdc++.h> using namespace std; int n; const int N=1e6+50; int a[N]; int Pow[N]; int num[N]; int mai...

#include <bits/stdc++.h> using namespace std; const int N=1e6+5; const int INF=0x3f3f3f3f; int n,x,y; char s[N]; int pre[N][2]; bool check(int m){  for(int i=1;i+m-1<=n;i++){  //xx yy是整个序列减去中间修改部分剩下的序列所对应的x和y int xx=pre[n][0]-pre[i+m-1][0]+pre[i-1][0]; int yy=pre[n][1]-pre[i+m-1][1]+pre[i-1...

第一圈读取所有数字的时候就可以去除那些加上sum大于T的了 然后记录去除后第一圈的和sum，直接取模 然后接下来也是重复同样的操作，当循环一次之后没有任何一个可以买的就退出while #include <bits/stdc++.h> using namespace std; typedef long long ll; int n; ll T; const int N=2*1e5+50; int a[N]; bool vis[N]; int x; int main(void){  //freopen("data.txt","r",stdin);...

不会树形dp #include <bits/stdc++.h> using namespace std; const int N=2e3+50; const int MOD=998244353; typedef long long ll; int n,k; int u,v; int cnt; int head[N]; struct Edge{  int v,next; }edge[N<<1]; void init(){  cnt=0; memset(head,-1,sizeof(head)); } void addEdge(int u,int v){  edge[cnt...

hdu的不要62那道题 import java.util.Scanner; public class Main {  static int[] a = new int[20]; //dp[pos][sta]表示当前第pos位，前一位是否为6的状态 static int[][] dp = new int[20][2]; //当前位数 上一个数 当前状态(上一位是否为6) 是否有枚举上界 static int dfs(int pos, int pre, int sta, boolean limit) {  //枚举结束 if (pos == -1) {  return 1; } //记忆化 if ...

poj2342 最简单的树形dp入门，树上的最大点权独立集 #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=6e3+50; const int M=2e4+50; struct Edge{  int v,next; }edge[M]; int cnt,head[N]; //dp[i][1/0]表示该点取或不取所能获得的最大权值 int dp[N][2]; int n,u,v; bool ind[N]; void init(){...

最简单的树形dp，树上最大点权独立集 import java.util.Scanner; public class Main{  static class Edge{  int v,next; Edge(int v,int next){  this.v=v; this.next=next; } } static final int N=(int)6e3+50; static final int M=(int)2e4+50; static int n,u,v,cnt; static int[] head=new int[N]; static int[][] dp=new int[N][2]; s...