T1:
我们可以用火柴棒来表示十进制下的0~9, 如图所示
现给定火柴数n, 问用这n根火柴能组成的最小数和最大数分别是多少. 所有火柴必须全部用完, 并且所有数字必须是正的且不含前缀零.
【解题】
首先最大数，我们要让位数最多，那么如果n是偶数，那么输出n/2个1，否则就在前面加上个7 然后输出个1
最小的数，有点难办，我们发现前三位都是循环，然后剩下火柴数量都是7的倍数，要使答案尽量小，再后面加上若干个8即可
#include<map> #include<stack> #include<queue> #include<cstdio> #include<string> #include<vector> #include<cstring> #include<complex> #include<iostream> #include<assert.h> #include<algorithm> using namespace std; #define inf 1001001001 #define infll 1001001001001001001LL #define FOR0(i,n) for(int (i)=0;(i)<(n);++(i)) #define FOR1(i,n) for(int (i)=1;(i)<=(n);++(i)) #define ll long long #define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl #define gmax(a,b) (a)=max((a),(b)) #define gmin(a,b) (a)=min((a),(b)) #define ios0 ios_base::sync_with_stdio(0) #define Ri register int #define gc getchar() #define il inline il int read(){ bool f=true; Ri x=0;char ch; while(!isdigit(ch=gc))if(ch=='-')f=false; while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=gc;} return f?x:-x; } #define gi read() #define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout); int ten[]={0,inf,1, 7, 4, 2, 6, 8, 10, 18, 22}; int cir[]={200,20,2,6,0,10,1}; int cirr[]={17,11,5,6,0,8,2}; int main(){ FO(match); int T=gi; while(T--){ RI(n); int _n=n; if(n<=10) printf("%d ",ten[n]); else{ if(cir[(n-10)%7]) cout<<cir[(n-10)%7]; n=n-cirr[(n-10)%7]; while(n){ cout<<8;n-=7; }cout<<' '; } n=_n; if(n&1){putchar('7');n-=3;} while(n){putchar('1');n-=2;}putchar(' '); } return 0; }
T2
定义从一个点(x, 0)到一个线段[L, R]的覆盖范围, 是若x < L 或x > R, 则覆盖范围为0; 否则, 覆盖范围为min(x – L, R – x).
现给你n个线段[Li, Ri], 以及m组询问. 每组询问包含一个点(xi, 0), 求该点到所有线段的覆盖范围中的最大值.
【解题】
离散化所有询问
左端点变成[L,mid] 右端点变成[mid+1,R]，询问的鬼东西就是堆中的最值（建议使用multiset
/*没有代码*/
T3
一行总共长度为n米的长龙, 由公共汽车组成, 可能是长度为5米的短车, 也可能是长度为10米的长车. 短车有k种不同的染色方法, 长车有l中不同的染色方法. 问这一行可能有多少种不同的样子?
【解题】
首先长度5和10可以变成1和2
那么很显然的递推式
答案就是
然后我们一看n<=，看这个式子可以用矩阵乘法优化计算复杂度
然后只要求大概这样，然后没了
#include<map> #include<stack> #include<queue> #include<cstdio> #include<string> #include<vector> #include<cstring> #include<complex> #include<iostream> #include<assert.h> #include<algorithm> using namespace std; #define pb push_back #define inf 1001001001 #define infll 1001001001001001001LL #define FOR0(i,n) for(int (i)=0;(i)<(n);++(i)) #define FOR1(i,n) for(int (i)=1;(i)<=(n);++(i)) #define mp make_pair #define pii pair<int,int> #define ll long long #define ld double #define vi vector<int> #define SZ(x) ((int)((x).size())) #define fi first #define se second #define RI(n) int (n); scanf("%d",&(n)); #define RI2(n,m) int (n),(m); scanf("%d %d",&(n),&(m)); #define RI3(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k)); template<typename T,typename TT> ostream& operator<<(ostream &s,pair<T,TT> t) {return s<<"("<<t.first<<","<<t.second<<")";} template<typename T> ostream& operator<<(ostream &s,vector<T> t){FOR0(i,sz(t))s<<t[i]<<" ";return s; } #define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl #define all(t) t.begin(),t.end() #define FEACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define TESTS RI(testow)while(testow--) #define FORZ(i,a,b) for(int (i)=(a);(i)<=(b);++i) #define FORD(i,a,b) for(int (i)=(a); (i)>=(b);--i) #define gmax(a,b) (a)=max((a),(b)) #define gmin(a,b) (a)=min((a),(b)) #define ios0 ios_base::sync_with_stdio(0) using namespace std; #define Ri register int #define gc getchar() #define il inline il int read(){ bool f=true; Ri x=0;char ch; while(!isdigit(ch=gc))if(ch=='-')f=false; while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=gc;} return f?x:-x; } #define gi read() #define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout); ll MOD=1000000; struct Matrix{ ll a[2][2]; ll* operator[](int x){return a[x];} }; Matrix operator*(Matrix a,Matrix b){ Matrix s; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ ll ans=0; for(int k=0;k<2;k++) ans+=a[i][k]*b[k][j]%MOD; s[i][j]=ans%MOD; } } return s; } Matrix Pow(Matrix s,ll d){ Matrix ans; for(int i=0;i<2;i++) ans[i][i]=1; while(d){ if(d&1) ans=ans*s; s=s*s; d>>=1; } return ans; } int main(){ freopen("color.in","r",stdin); freopen("color.out","w",stdout); ll n,k,l; while(scanf("%lld%lld%lld",&n,&k,&l)!=EOF){ n/=5;k%=MOD;l%=MOD; Matrix s; s[0][0]=0;s[0][1]=l; s[1][0]=1;s[1][1]=k; Matrix qq=Pow(s,n); ll ans=(qq[1][1]%MOD+MOD)%MOD; printf("%06d ",ans); } }