A - 小L的作文
题意
给一个字符x和一个字符串b 然后去找b中x出现了几次
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
int main(void){
char a , b;
cin>>a;
getchar();
ll ans = 0;
while(scanf("%c" , &b) && b != '\n'){
if(b == a) ans++;
}
cout<<ans<<endl;
return 0;
} B - 小L的多项式
题意
简单来说就是给出一个多项式 然后给一个数字让你把这个数字带到这个多项式里求值 多项式是规律的 即这样
有多少个就有多少项（加一项，还有0次方）
并且数据范围较小 直接暴力即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[N];
int main(void){
int n , m;
scanf("%d" , &n);
for(int i = 1 ; i <= n + 1 ; ++i){
scanf("%d" , &a[i]);
}
scanf("%d" , &m);
ll k = 0;
for(int i = 1 ; i <= m ; ++i){
ll ans = 0;
scanf("%lld" , &k);
for(int j = 1 ; j <= n + 1 ; ++j){
ans += a[j] * qpow(k , j - 1 , mod) % mod;
ans %= mod;
}
printf("%lld%c" , ans , i == m ? '\n' :' ');
}
return 0;
} 这是我比赛的时候的代码 然后还有更快的做法
即因为是不断地从一次方二次方三次方这样乘上来 因此我们可以保存上一次的结果然后用到下一次 这样就不用每次都
一下了 速度会快很多
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[N];
int main(void){
int n , m;
scanf("%d" , &n);
for(int i = 1 ; i <= n + 1 ; ++i){
scanf("%d" , &a[i]);
}
scanf("%d" , &m);
ll k = 0;
for(int i = 1 ; i <= m ; ++i){
ll ans = 0;
scanf("%lld" , &k);
ll t = 1;
for(int j = 1 ; j <= n + 1 ; ++j){
ans += a[j] * t % mod;
t = (t * k) % mod;
ans %= mod;
}
printf("%lld%c" , ans , i == m ? '\n' :' ');
}
return 0;
} C - 小L的编辑器
题意
给出两个字符串a ，b，然后a中的字符按照b的规律输出，即有一个光标，每一次输出之后，光标停的位置按照b的顺序
即 a中为 ab
b为LR
那么第一次输出之后就是 |a
然后再输出b就是在a的左边
即输出之后就是 b|a
如果这个时候还是有一个c 然后对应b中是L
那么就是b|ca
到现在为止如果直接去模拟 不仅时间复杂度裂开而且挺难模拟的
我们直接观察 以光标为分界线 其实不难看出 在右边的就是谁先进来就排在后面 左边的就是谁先进来就谁排在前面 所以很明显了
当输入L的时候就把字符插到一个栈中 输入R的时候 就插到队列中 然后把栈和队列按顺序输出就好了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
int main(void){
string a , b;
cin>>a>>b;
stack<char>st1;
queue<char>st2;
for(int i = 0 ; i < a.size() ; ++i){
if(b[i] == 'L'){
st1.push(a[i]);
}
else{
st2.push(a[i]);
}
}
while(st2.size()){
cout<<st2.front();
st2.pop();
}
while(st1.size()){
cout<<st1.top();
st1.pop();
}
return 0;
} D - 小L的数列
题意
给出个数 要求从中挑出一些数来组成一个数列 要求排在前面的小于后面的并且相邻的两个数字不互质
要不互质那么我们就要求取出来的数字两个之间有相同的因子，因此我们可以先把所有的素数筛出来，然后我们去找那些数字有这个素数作为因子的，再找数字的时候 我们可以记录这个数字的下一个用相同因子的素数
我们只需要找到下一个有着相同的因子的数即可 然后进行dp
然后这个代码应该是目前最快的了
几个加速的地方 桶排 因为数据卡的很那个 所以用桶排是比直接sort要快的
然后dp的优化 因为上面也说了 我们只要把上一个和他有相同因子的转移过来就可以了
然后筛素数的时候 只需要筛到 就可以了 因为后面不会再出现这个素数的倍数了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 7;
bool vis[maxn];
vector<int>prime;
int i ;
inline int max(int a,int b) {
return a>b?a:b;
}
inline void initial() {
for (i = 2; 2 * i < maxn ; ++i) {
if (!vis[i])
prime.push_back(i);
for (int j = 0,size=prime.size(); j < size; ++j) {
if (i * prime[j] >= maxn) break;
vis[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
}
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
int a[N] , dp[N] , last[N];
int main(void){
initial();
int T = read() , n , k;
while(T--){
n = read();
memset(last , 0 , sizeof(last));
memset(a , 0 , sizeof(a));
for(int i = 1 ; i <= n ; ++i){
k = read();
a[k] = 1;
}
int m = 0;
int res = 1;
for(i = 2 ; i <= 100000 ; ++i){
if(a[i] == 0) continue;
dp[i] = 1;
int y = i;
for(auto x : prime){
if(x > y) break;
if(!vis[y]){
if(last[y]){
dp[i] = max(dp[i] , dp[last[y]] + 1);
}
last[y] = i;
break;
}
if(y % x == 0){
if(last[x]){
dp[i] = max(dp[i] , dp[last[x]] + 1);
}
last[x] = i;
while(y % x == 0) y /= x;
}
}
res = max(res , dp[i]);
}
printf("%d\n" , res);
}
return 0;
} 
京公网安备 11010502036488号