A 夹娃娃
题意：给你n个排列好的娃娃，并给你每个娃娃的价值，求l-r这个区间的娃娃价值(包括l和r)？
题解：知识点：前缀和
直接就是维护一个前缀和，然后做差就是他区间的中价值，没啥好说的。
代码:
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;
#define read read()
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i],dis[i]=dis[i-1]+a[i];
while(m--){
cin>>l>>r;
cout<<dis[r]-dis[l-1]<<endl;
}
return 0;
}
B-莫的难题
题意：有5个数字 1，2,3,5,9在这我5数字你可以选择任意数字来组成数，问你第%251e9%2B7 "图片标题")
%1e9+7小的数是几？
据反映这个题比较难，感觉可能是没get这个题的点吧。 题解：知识点：组合数 首先要求组合数，因为数据量是100所以可以直接组合数打表，这是没有一点问题的。
然后下一不就是找这个数。我们这样看：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...... 1 2 3 5 9 11 12 13 15 19 21 22 23 25 29 31.....
通过我上面列的你是否看出有什么端倪那？
我们可以看到1，2,3,5，9，其实是循环出现的，以5为周期，来变化，
一位数有5^1
两位数有5^2
三位数有5^3
....
知道这些还是不能解决这些问题，我们在深入一步。
既然他是5为周期的我们是不是一位一位的给她确定下来，这样就能的到最终的数。
第一步很好想就是%5，这就是个位，
然后确定十位，/5在进行循环，这时就出现问题了，就像第十小的数一样，它反映出来是29而不是19，
因为当我们确定十位是我们/5，因为各位是整除的关系，所以就是/5之后遗留到十位，导致十位被迫进位，所以当我们整除时只需要，把遗留在十位的那部分减去就行了。
其实说简单点就是整除是，会导致进位，所以下一位减1；
这样我们所有的问题就解决了，剩下的就是倒序输出就行了。
代码：
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=1e9+7;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;
void get_C(int ma)
{
dp[0][0] = 1;
for(int i=1;i<=ma;i++)
{
dp[i][0] = 1;
for(int j=1;j<=i;j++)
// C[i][j] = C[i-1][j]+C[i-1][j-1];
dp[i][j] = (dp[i-1][j]+dp[i-1][j-1])%mod;
}
}
#define read read()
int main(){
get_C(1000);
a[1]=1;
a[2]=2;
a[3]=3;
a[4]=5;
a[0]=9;
sf("%lld",&t);
while(t--){
sf("%lld%lld",&n,&m);
sum=dp[n][m];
//cout<<sum<<endl;
p=0;
while(sum){
dis[++p]=sum%5;
if(dis[p]==0)
sum=sum/5-1;
else sum/=5;
}
for(int i=p;i>=1;i--)
{
pf("%lld",a[dis[i]]);
}
pf("\n");
}
return 0;
}
C-不平衡数组
题意：给出一串数，和修改它的代价，但修改只能是加一，要求相邻的数不相等，求代价最小？
题解：知识点：DP
直接就是Dp表示就可以了，二维空间，dp[i,j],i表示第几个，j表示状态，是否加1.
然后分析：
两个相邻的数，对应着四种状态：
两个相邻的数用，x，y来表示
1，x，y。都不加
2，x，y+1.前一个不加，后一个加
3，x+1，y。前一个加，后一个不加
4，x+1，y+1。都加。
这四个状态，就产生了四个状态转移方程
if(a[i]!=a[i-1]) dp[i][0]=min(dp[i][0],dp[i-1][0]);
//如果与前面位置的数不相等，就可以从前面那个位置不加一状态转移过来
if(a[i]!=a[i-1]+1) dp[i][0]=min(dp[i][0],dp[i-1][1]);
///如果与前面位置的数+1 不相等，就可以从前面位置+1状态转移过来
if(a[i]+1!=a[i-1]) dp[i][1]=min(dp[i][1],dp[i-1][0]+b[i]);
///如果这个数+1与前面位置的数不相等，就可以从前位置不加状态转移过来当然要加上这个数+1的代价
if(a[i]+1!=a[i-1]+1) dp[i][1]=min(dp[i][1],dp[i-1][1]+b[i]);
///如果这个数+1与前面位置的数+1不相等，就可以从前位置+1状态转移过来当然要加上这个数+1的代价代码：
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[maxn][2];
string str,s;
struct node {
ll a,b;
ll id;
}q[maxn];
#define read read()
int main() {
sf("%lld",&n);
for(int i=1; i<=n; i++) {
sf("%lld%lld",&a[i],&b[i]);
dp[i][1]=dp[i][0]=1e18;
}
//dp[i][j] i表示第几个，j表示加不加1,0不加，1加
dp[1][0]=0;dp[1][1]=b[1];
for(int i=2;i<=n;i++){
//相邻不相同
if(a[i]!=a[i-1]) dp[i][0]=min(dp[i][0],dp[i-1][0]);
if(a[i]!=a[i-1]+1) dp[i][0]=min(dp[i][0],dp[i-1][1]);
if(a[i]+1!=a[i-1]) dp[i][1]=min(dp[i][1],dp[i-1][0]+b[i]);
if(a[i]+1!=a[i-1]+1) dp[i][1]=min(dp[i][1],dp[i-1][1]+b[i]);
}
pf("%lld\n",min(dp[n][1],dp[n][0]));
return 0;
}
D-数列统计
题意：求以x结尾的长度为l的不下降正整数数列一共有多少个。对911451407911451407取模？
题解：知识点：阶乘逆元
我们先列出来一部分
l: 1 x:1 1 l: 1 x:n 1 l: 2 x:1 1 l: 2 x:2 2 l: 2 x:3 3 l: 2 x:4 4 l: 3 x:1 1 l: 3 x:2 3 l: 3 x:3 6 l: 3 x:4 10 l: 3 x:5 15
通过上述可以看出规律就是
然后我们就是求这个组合数，就是(l+x-2)阶乘/(l-1)的阶乘/(x-1)的阶乘，在用你逆元的知识，就换成(l+x-2)阶乘(l-1)的逆元(x-1)的逆元。
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e6+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=911451407;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;
ll qpow(ll a,ll b){
ll sum=1;
while(b){
if(b&1) sum=sum*a%mod;
b>>=1;
a=a*a%mod;
}
return sum;
}
void into(){
a[0]=1;
for(int i=1;i<maxn;i++)
a[i]=a[i-1]*i%mod;//阶乘
b[maxn-1]=qpow(a[maxn-1],mod-2);
//逆元
for(int i=maxn-2;i>=1;i--){
b[i]=b[i+1]*(i+1)%mod;//阶乘逆元
}
}
#define read read()
int main(){
into();
sf("%lld",&t);
while(t--){
sf("%lld%lld",&l,&r);
if(l==1||r==1){
cout<<1<<endl;
}else {
l--;r--;
pf("%lld\n",a[l+r]*b[l]%mod*b[r]%mod);
}
}
return 0;
}
京公网安备 11010502036488号