Codeforces 916 二进制1数目构造(阅读理解) 最小生成树1-N路径质数构造-白红宇

Codeforces 916 二进制1数目构造(阅读理解) 最小生成树1-N路径质数构造

阅读量：4356 次

发布时间：2019-06-07

本文共 3501 字，大约阅读时间需要 11 分钟。

#include 
      
       #define PI acos(-1.0)#define mem(a,b) memset((a),b,sizeof(a))#define TS printf("!!!\n")#define pb push_back#define inf 1e9//std::ios::sync_with_stdio(false);using namespace std;//priority_queue
       
        
         ,greater
         
          > que; get minconst double eps = 1.0e-10;const double EPS = 1.0e-4;typedef pair
          
            pairint;typedef long long ll;typedef unsigned long long ull;const int turn[4][2] = {
    {
    1, 0}, { -1, 0}, {
    0, 1}, {
    0, -1}};//priority_queue

, less

> que;//next_permutationll mod = 3e7;const int MAXN=505;bool check(int x,int y){ if(x%10==7) return true; if(y%10==7) return true; return false;}int main(){ int n; int h,m; cin >> n >> h >> m; int cur=0; for(cur=0;!check(h,m);cur++) { m-=n; if(m<0) m+=60,h--; if(h<0) h+=24; } cout<

View Code

给你一个N 要求你分解成二进制的K个数并且要求你求出字典序尽量小情况下最大的答案

当原来1的数量>=k时答案很明显

当1的数量<k时因为要最小字典序所以前面的要尽量小要把最前面的1尽量全部变成后面的

当最前面的1的数量大于剩下的k时就不能继续转化了转化了字典序就不是尽量小情况下的最大答案了

应该转化最后的一个1直到满足答案这样字典序才是最大的

#include 
      
       #define PI acos(-1.0)#define mem(a,b) memset((a),b,sizeof(a))#define TS printf("!!!\n")#define pb push_back#define inf 1e9//std::ios::sync_with_stdio(false);using namespace std;//priority_queue
       
        
         ,greater
         
          > que; get minconst double eps = 1.0e-10;const double EPS = 1.0e-4;typedef pair
          
            pairint;typedef long long ll;typedef unsigned long long ull;const int turn[4][2] = {
    {
    1, 0}, { -1, 0}, {
    0, 1}, {
    0, -1}};//priority_queue

, less

> que;//next_permutationpriority_queue

, less

> que;ll mod = 3e7;const int MAXN = 505;int er[100200],*aim = er+100002;int main(){ ll n; int k; cin >> n >> k; for(int i=0;i<=60;i++) { k-=aim[i]=(n>>i)&1; } if(k<0) { cout<<"No"<

=-100;i--) { if(aim[i]) cout<

<<" "; } cout<

=-100;i--) { if(k>=aim[i]) { aim[i-1]+=2*aim[i]; k-=aim[i]; aim[i]=0; } else { int cur=-100000; while(!aim[cur]) cur++; for(int j=1;j<=k;j++) { aim[cur-1]+=2; aim[cur--]--; } break; } } cout<<"Yes"<

=-100000;i--) while(aim[i]) cout<
<<" ",aim[i]--;}

View Code

给你N个点和M条边要去你输出M条边使得1到N的最短路长度是质数最短生成树的值是质数

可以找个很大的质数使得除了N-1与N的值为质数-（N-1）而其他i与i+1相连的值是1 剩下要构造的其他边直接取很大的值就可以了

#include 
      
       #define PI acos(-1.0)#define mem(a,b) memset((a),b,sizeof(a))#define TS printf("!!!\n")#define pb push_back#define inf 1e9//std::ios::sync_with_stdio(false);using namespace std;//priority_queue
       
        
         ,greater
         
          > que; get minconst double eps = 1.0e-10;const double EPS = 1.0e-4;typedef pair
          
            pairint;typedef long long ll;typedef unsigned long long ull;const int turn[4][2] = {
    {
    1, 0}, { -1, 0}, {
    0, 1}, {
    0, -1}};//priority_queue

, less

> que;//next_permutationpriority_queue

, less

> que;ll mod = 3e7;const int MAXN = 505;int pop = 1;int prime;bool ok(int x){ for (int i = 2; i <= (int)sqrt(x); i++) { if (x % i == 0) { return false; } } return true;}int main(){ int want = 1e9; int n, m; for (int i = 100000; i <= 1000000; i++) { if (ok(i)) { prime = i; break; } } cin >> n >> m; cout << prime << " " << prime << endl; m -= n - 1; for (int i = 1; i <= n - 2; i++) { cout << i << " " << i + 1 << " " << 1 << endl; } prime -= n - 2; cout << n - 1 << " " << n << " " << prime << endl; for (int i = 2; i <= n - 1 && m; i++) { for (int j = 1; j <= n - i && m; j++, m--) { cout << j << " " << j + i << " " << want << endl; } }}

View Code