首页 > 其他分享 >2022.11.11

2022.11.11

时间：2022-11-12 16:13:13浏览次数：73  
标签：11 return int long operator const 2022.11 define

今天，全校都去秋游了，只有 Oier 还在训练。

P5004 专心OI - 跳房子

其实就是前一天那道P5059 中国象棋 的加强版。

状态转移方程也就略有变动： \(f_i = \sum_{j=1}^{i-m-1} f_j = f_{i-1}+f_{i-m-2}\)
注意到 \(m\) 很小，不难想到，直接把目前 \(m\) 个元素全都加入矩阵，最后把当前矩阵的数值累加即可。

code 
// I forgot all the tragedies and all I saw were miracles.

/************************************
|* Author:  A.I.skeleton
|* Problem: P5004 专心OI - 跳房子
|* Contest: Luogu
|* URL:     https://www.luogu.com.cn/problem/P5004
|* When:    2022-11-10 20:59:34
|* 
|* Memory:  125 MB
|* Time:    1000 ms
************************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define lc p<<1
#define rc p<<1|1
#define lb(x) (x&-x)
#define pb push_back
#define ch(i) (i-'a')
#define vi vector<int>
#define F(i) (i).first
#define S(i) (i).second
#define X(i) (i>n?i-n:i)
#define pi pair<int,int>
#define id(x,y) ((x-1)*m+y)
#define cl(x) ((x).clear());
#define si(i) ((int)i.size())
#define kw(x,k) (((x)>>(k))&1)
#define all(x) (x).begin(),(x).end()
#define me(t,x) memset(t,x,sizeof(t))
#define L(i,j,k) for(int (i)=(j);i<=(k);(i)++)
#define R(i,j,k) for(int (i)=(j);i>=(k);(i)--)
#define ll(i,j,k,l) for(int (i)=(j);i<=(k);(i)+=(l))
#define rr(i,j,k,l) for(int (i)=(j);i>=(k);(i)-=(l))
#define dout(a,x) cout<<fixed<<setprecision(x)<<a<<'\n';
#define FST ios::sync_with_stdio(false);cin.tie(nullptr);

#define DE
#pragma GCC optimize(2)

namespace DG{
#ifdef DE
#define got cout<<"get here"<<'\n';
#define cut cout<<"-------------------------\n";
#define time cerr<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n",0;
#define dgvi(v) cout<<#v": size= "<<si(v)<<"\nelement: ";for(auto p:v) cout<<p<<" ";cout<<'\n';
#define dgar(x,s) cout<<#x": len= "<<s+1<<"\nelement: ";L(i,0,s) cout<<x[i]<<" \n"[i==s];
#define dge(x,n) int _=0;L(i,0,n) _+=si(x[i]);cout<<"There are "<<_<<" edges in "<<#x<<'\n';\
                 L(u,0,n) for(int v:x[u]) cout<<u<<' '<<v<<'\n';
#define dg(...) W(#__VA_ARGS__,__VA_ARGS__)
template<typename ...Args>
void W(string X,Args&&...V){cout<<X<<" = ";string D=""; (...,(cout<<D<<V,D=", "));cout<<'\n';}
#else 
#define got
#define time 0
#define cut
#define dgvi(v)
#define dgar(x,s)
#define dge(x,n)
#define dg(...)
#endif 
}using namespace DG;namespace IO{
template<typename T>void rd(T &x){cin>>x;}template<typename T>void wr(T x){cout<<x;}
template<typename T,typename ...Args>void rd(T &x,Args &...args){rd(x),rd(args...);}
template<typename T,typename ...Args>void wr(T x,Args ...args){wr(x),wr(args...);}
}using namespace IO;
int mod=1e9+7;
#define P ((int)mod)
int O(int x){return x<0?(x+=P):x<P?x:(x-=P);}
template<class T>
T ksm(T a,ll b){T s=1;for(;b;b>>=1,a*=a) if(b&1) s*=a;return s;}
struct Z{
  int x;Z(int x=0):x(O(x)){}Z(ll x):x(O(x%P)){}
  bool operator<(const Z&b)const{return x<b.x;}
  bool operator>(const Z&b)const{return x>b.x;}
  bool operator<=(const Z&b)const{return x<=b.x;}
  bool operator>=(const Z&b)const{return x>=b.x;}
  bool operator==(const Z&b)const{return x==b.x;}
  bool operator!=(const Z&b)const{return x!=b.x;}
  int val()const{return x;}bool operator!(){return !x;}
  Z operator-()const{return Z(O(P-x));}
  Z inv()const{assert(x!=0);return ksm(*this,P-2);}
  Z&operator++(){return x=O(x+1),*this;}
  Z&operator--(){return x=O(x-1),*this;}
  Z&operator*=(const Z&r){x=(ll)(x)*r.x%P;return*this;}
  Z&operator+=(const Z&r){x=O(x+r.x);return*this;}
  Z&operator-=(const Z&r){x=O(x-r.x);return*this;}
  Z&operator/=(const Z&r){return*this*=r.inv();}
  Z&operator+=(const int &r){x=O(x+r);return *this;}
  Z&operator-=(const int &r){x=O(x-r);return *this;}
  Z&operator*=(const int &r){x=(ll)(x)*r%P;return *this;}
  Z&operator/=(const int &r){Z x=r;return *this*=x.inv();}
  friend Z operator*(const Z&l,const Z&r){Z s=l;s*=r;return s;}
  friend Z operator+(const Z&l,const Z&r){Z s=l;s+=r;return s;}
  friend Z operator-(const Z&l,const Z&r){Z s=l;s-=r;return s;}
  friend Z operator/(const Z&l,const Z&r){Z s=l;s/=r;return s;}
  friend Z operator*(const Z&l,const int&r){Z s=l;s*=r;return s;}
  friend Z operator+(const Z&l,const int&r){Z s=l;s+=r;return s;}
  friend Z operator-(const Z&l,const int&r){Z s=l;s-=r;return s;}
  friend Z operator/(const Z&l,const int&r){Z s=l;s/=r;return s;}
  Z &operator^=(int b){
    Z a=*this,c=1;for(;b;b>>=1,a*=a) if(b&1) c*=a;
    return x=c.x,*this;
  }friend Z operator^(Z a,int b){return a^=b;}
  friend istream&operator>>(istream&is,Z&a){ll v;is>>v;a=Z(v);return is;}
  friend ostream&operator<<(ostream&os,const Z&a){return os<<a.val();}
};
#define int long long
const int N=2e6+100,INF=1e18;
int n,m;Z ans;
struct mt{
  Z a[20][20];mt(){me(a,0);}
  friend mt operator*(mt a,mt b){
    mt c;L(i,0,16) L(j,0,16) L(k,0,16)
      c.a[i][j]+=a.a[i][k]*b.a[k][j];return c;
  }
}b,s;
void power(int k){for(;k;k>>=1,b=b*b) if(k&1) s=s*b;}
void init(){
  b.a[1][1]=b.a[m+1][1]=1;
  L(i,1,m) b.a[i][i+1]=1;
}signed main(){
  FST;rd(n,m);init();
  L(i,1,m+1) s.a[1][i]=1;
  if(n<=m){wr(2,'\n');return time;}
  power(n-m);L(i,1,m+1) ans+=s.a[1][i];
  wr(ans,'\n');return time;
}

P3597 [POI2015] WYC

边权最大为 \(3\)，显然直接拆点建图。
一定要注意可能有重边，邻接矩阵一定是 ++ 而不是 =1
因为是全局的路径，所以引入一个超级源点 \(0\)，所有实点(不是拆点拆出的点)向源点连边，矩阵乘统计。
显然直接乘会 T，考虑来个倍增优化下。
注意要特判，如果超过 \(64\) 次倍增仍达不到，就直接判掉。
运算过程中可能会爆 long long，所以要时刻对 \(k\) 取 \(\min\)，或者直接用 \(__int128\)。

code 
// I forgot all the tragedies and all I saw were miracles.

/************************************
|* Author:  A.I.skeleton
|* Problem: P3597 [POI2015] WYC
|* Contest: Luogu
|* URL:     https://www.luogu.com.cn/problem/P3597
|* When:    2022-11-11 10:10:10
|* 
|* Memory:  128 MB
|* Time:    1000 ms
************************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define lc p<<1
#define rc p<<1|1
#define lb(x) (x&-x)
#define pb push_back
#define ch(i) (i-'a')
#define vi vector<int>
#define F(i) (i).first
#define S(i) (i).second
#define X(i) (i>n?i-n:i)
#define pi pair<int,int>
#define id(x,y) ((x-1)*m+y)
#define cl(x) ((x).clear());
#define si(i) ((int)i.size())
#define kw(x,k) (((x)>>(k))&1)
#define all(x) (x).begin(),(x).end()
#define me(t,x) memset(t,x,sizeof(t))
#define L(i,j,k) for(int (i)=(j);i<=(k);(i)++)
#define R(i,j,k) for(int (i)=(j);i>=(k);(i)--)
#define ll(i,j,k,l) for(int (i)=(j);i<=(k);(i)+=(l))
#define rr(i,j,k,l) for(int (i)=(j);i>=(k);(i)-=(l))
#define dout(a,x) cout<<fixed<<setprecision(x)<<a<<'\n';
#define FST ios::sync_with_stdio(false);cin.tie(nullptr);

// #define DE
// #pragma GCC optimize(2)

namespace DG{
#ifdef DE
#define got cout<<"get here"<<'\n';
#define cut cout<<"-------------------------\n";
#define time cerr<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n",0;
#define dgvi(v) cout<<#v": size= "<<si(v)<<"\nelement: ";for(auto p:v) cout<<p<<" ";cout<<'\n';
#define dgar(x,s) cout<<#x": len= "<<s+1<<"\nelement: ";L(i,0,s) cout<<x[i]<<" \n"[i==s];
#define dge(x,n) int _=0;L(i,0,n) _+=si(x[i]);cout<<"There are "<<_<<" edges in "<<#x<<'\n';\
                 L(u,0,n) for(int v:x[u]) cout<<u<<' '<<v<<'\n';
#define dg(...) W(#__VA_ARGS__,__VA_ARGS__)
template<typename ...Args>
void W(string X,Args&&...V){cout<<X<<" = ";string D=""; (...,(cout<<D<<V,D=", "));cout<<'\n';}
#else 
#define got
#define time 0
#define cut
#define dgvi(v)
#define dgar(x,s)
#define dge(x,n)
#define dg(...)
#endif 
}using namespace DG;

const int N=2e6+100,INF=1e9;
#define int __int128
void wr(int x){
  if(x<0)x=-x,putchar('-');
  if(x>9)wr(x/10);
  putchar(x%10+48);
}void rd(int &x){
  x=0;char ch=getchar();
  for(;!isdigit(ch);ch=getchar());
  for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
}int n,m,k,u,v,w,ans;
struct mt{
  int a[150][150];mt(){me(a,0);}
  friend mt operator*(mt a,mt b){
    mt c;L(k,0,n*3) L(i,0,n*3) L(j,0,n*3) 
      c.a[i][j]+=a.a[i][k]*b.a[k][j];return c;
  }
}b[80],s,g;
signed main(){//(x-1)*3+1 to unique
  rd(n);rd(m);rd(k);
  b[0].a[0][0]=1;
  L(i,1,n){
    s.a[0][(i-1)*3+1]=1;b[0].a[(i-1)*3+1][0]=1;
    b[0].a[(i-1)*3+2][(i-1)*3+1]=1;
    b[0].a[(i-1)*3+3][(i-1)*3+2]=1;
  }L(i,1,m) rd(u),rd(v),rd(w),b[0].a[(u-1)*3+1][(v-1)*3+w]++;
  int x;L(i,1,INF){
    x=i;b[i]=b[i-1]*b[i-1];g=s*b[i];
    if(g.a[0][0]-n>=k) break;
    if(i>=64) return puts("-1"),time;
  }R(i,x,0){
    g=s*b[i];
    if(g.a[0][0]-n<k) 
      s=g,ans+=(1ll<<i);
  }wr(ans);putchar(10);
  return time;
}

GSS6 - Can you answer these queries VI

其实就是 P2042 [NOI2005] 维护数列 的弱化版本，直接 FHQ-Treap 干上去即可。
但码力不及当年，\(\color{Red}{WA}\) 了好几发才过去。

剩余时间都在摆。

标签：11,return,int,long,operator,const,2022.11,define
From： https://www.cnblogs.com/AIskeleton/p/16883985.html

相关文章

  • Linux-0.11操作系统源码调试
    学习操作系统有比较好的两种方式，第一种是跟着别人写一个操作系统出来，《操作系统真相还原》、《Orange's:一个操作系统的实现》等书就是教学这个的；另一种方式就是调试操作系......
  • EF-Blind box 2022-11-07 TO 2022-11-13
    1onlineunit-->01privatelesson-->2PLdone7grouplesson-->6grouplesson1F2F-->4F2Fdone1LfeClub-->2LCdone1Workshop-->done......
  • 20221112 - Find Device closed unexpectedly 问题解决
    问题现象：小米手机屏幕下方每隔2秒弹出 FindDeviceclosedunexpectedly问题解决：备份数据；并恢复出厂设置（开机前，按住音量键上或下+开机键）。备注：也尝试了一些网上的说法......
  • After Effects 2022.11.12
    菜单栏：窗口-->效果和预设菜单栏：效果-->扭曲-->波形变形新建一个蓝色的纯色层，拖动波形变形的效果。波浪类型，正方形。设置波形宽度400，设置方向为0，波形速度5.0设置波形高......
  • 2022/11/07-13 训练小记
    2022/11/07-13训练小记P7961[NOIP2021]数列显然是一个\(dp\)，首先考虑状态应如何设计。看到\(n\)的限制，首先可以想到记一维\(i\)表示当前已被确定的\(a\)序列......
  • 从 Ynoi2011 初始化 看卡常
    一般情况下，程序运行消耗时间主要与时间复杂度有关，超时与否取决于算法是否正确。但对于某些题目，时间复杂度正确的程序也无法通过，这时我们就需要卡常数，即通过优化一些操作的......
  • 周六900C++班级2022-11-12-搜索练习
    KnightMoves#include<bits/stdc++.h>usingnamespacestd;intnex[8][2]={{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};//方向数组intvis[310][3......
  • 11.feign性能优化
    feign性能优化连接池配置，feign添加httpClient的支持1.引入依赖<!--httpClient的依赖--><dependency><groupId>io.github.openfeign</groupId>......
  • 11. 跨域怎么解决
    首先，跨域分为开发环境和生产环境的跨域，我们在开发环境可以使用proxy代理给target设置请求接口地址，以前使用的是jsonp跨域；生产环境使用Nginx反向代理； 延申问......
  • 2022-11-11 这10天，纳斯达克V形反转的一点记录
    1.从11月2号开始，首先已经跌破上升趋势线2.联席会议开始，多头突然发力，2段上涨3.结果空头发力，多空争夺激烈。空头回落到多头的1/2甚至2/3以下，一定要出了！开盘，收盘，事件，会......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99