2022—SWJTU寒假选拔赛第五场复盘
又是一篇迟到许久的复盘，终于在回到学校的第一天补上了。
链接
题目列表
A - CodeForces 114E 很强的素数 ×
题目大意：
给定区间[L,R]，求区间内满足条件的数的个数：
条件1）z是素数
条件2）z=x2+y2 x和y为任意的正整数
解题思路：
其实就是求满足费马定理的数的个数。
**费马定理： 一个奇素数z可以表示成z=x2+y2的形式,当且仅当z可以表示成4*t+1的时候。（偶素数2=12+12）**
LR的范围是1到3*10^8用普通的筛选法求素数表，时间空间都会超。使用两次筛选来求素数。
3*10^8的平方根小于17500，用17500以内的素数可以筛出范围内的所有素数。在通过判断是否满足z=t%4+1来累加。
又由于z的范围过大，但对于唯一确定的z来说，t也唯一确定，故可以用t作为数组下标即(z-1)/4。数组大小就会小4倍左右。
具体细节看代码备注。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <bitset>
#define MAXN 17500
using namespace std;
bitset<MAXN>ISP; //类似于bool型，可以存01
bitset<300000000/4+10>result;
int prime[MAXN];
int is_prime()//先筛选1-17500的素数
{
int p=0;
ISP[0]=ISP[1]=1;
for (int i=1; i<=MAXN; i++)
if (ISP[i]==0)
{
prime[p++]=i;//用prime素组将素数存起来留到后面筛选用。。
for (int j=i+i; j<=MAXN; j+=i)
ISP[j]=1;
}
return p-1;
}
int cnt(int L,int R)
{
int p=is_prime();
for (int j=0; j<=p; j++)
{
int x=L/prime[j];
if (x*prime[j]<L) x++;
if (x==1) x++;
for (int k=x*prime[j]; k<=R; k+=prime[j]) //通过素数表再来筛选[L,R]中的素数
if (k%4==1) //标记符合条件2且不符合条件1的数
result[(k-1)/4]=1;
}
int cnt=0;
for (int i=L;i<=R;i+=4)
if (!result[(i-1)/4]) cnt++;
return cnt;
}
int main()
{
is_prime();
int L,R;
int ok=0;
cin>>L>>R;
if (L<=2&&R>=2) ok=1; //2作为偶素数且符合条件 单独判断
while (L%4!=1||L==1) //将区间边界缩小到符合 %4==1
L++;
while (R%4!=1)
R--;
cout<<cnt(L,R)+ok;
return 0;
}B - CodeForces 514C 字符串
思路一：哈希表
字符串hash
因为只有3个字符
所以权值就为3^x;
找个大质数取模就好；
不够大就再大一点。。
然后对于每一位,尝试换成其他两个字母,看看存不存在
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define ps push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x)
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 6e5+100;
const LL MOD = 1e12+7;
int n,m;
LL p[N];
string s;
set<LL> myset;
int main()
{
//freopen("F:\\rush.txt","r",stdin);
p[0] = 1;
rep1(i,1,N-2)
p[i] = (p[i-1]*3)%MOD;
rei(n),rei(m);
rep1(i,1,n)
{
cin >> s;
LL temp = 0;
int len = s.size();
rep1(j,0,len-1)
temp = (temp*3+s[j]-'0')%MOD;
myset.insert(temp);
}
rep1(i,1,m)
{
cin >> s;
bool ok = false;
int len = s.size();
LL temp = 0,ttemp;
rep1(j,0,len-1)
temp = (temp*3+s[j]-'0')%MOD;
rep1(j,0,len-1)
{
char t = s[j];
for (char d='a';d<='c';d++)
if (t!=d)
{
ttemp = (temp-(t-'0')*p[len-j-1])%MOD;
if (ttemp<0) ttemp=(ttemp+MOD)%MOD;
ttemp=(ttemp+(d-'0')*p[len-j-1])%MOD;
if (myset.count(ttemp))
{
ok = true;
break;
}
}
if (ok) break;
}
if (ok)
puts("YES");
else
puts("NO");
}
//printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}思路二：字典树
考虑字典树。
首先把n个单词插入字典树中。
询问的时候用dfs，flag表示搜索到当前是否已经改变过一个字符。
如果已经改变过那只能按照当前剩下的字符串一条路查询下去。
否则可以按老字符或新字符进行查询。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
const int N = 2e7 + 3;
char s[600010];
int n, q, ans, len, tot = 0;
int ch[N][3];
bitset <N> cnt;
int newnode(){
++tot;
rep(i, 0, 2) ch[tot][i] = 0;
cnt[tot] = 0;
return tot;
}
void insert(char* s){
int now = 0;
for (int i = 0; s[i]; ++i){
int w = s[i] - 'a';
if (!ch[now][w]) ch[now][w] = newnode();
now = ch[now][w];
}
cnt[now] = 1;
}
void dfs(int x, int flag, int now){
if (ans) return;
if (x == len && flag && cnt[now]){ ans = 1; return;}
if (x >= len) return;
if (flag){
int w = s[x] - 'a';
if (ch[now][w]) dfs(x + 1, flag, ch[now][w]);
}
else{
rep(i, 0, 2)
if (i != s[x] - 'a' && x + 1 == len && ch[now][i] && cnt[ch[now][i]]) ans = 1;
rep(i, 0, 2) if (i != s[x] - 'a' && ch[now][i]){
dfs(x + 1, 1, ch[now][i]);
}
int w = s[x] - 'a';
if (ch[now][w]){
dfs(x + 1, flag, ch[now][w]);
}
}
}
int main(){
scanf("%d%d", &n, &q);
rep(i, 1, n){
scanf("%s", s);
insert(s);
}
rep(i, 1, q){
scanf("%s", s);
len = strlen(s);
ans = 0;
dfs(0, 0, 0);
puts(ans ? "YES" : "NO");
}
return 0;
}C - CodeForces 243A 或 ×
我着实没想到真的用枚举
思路一: 枚举+剪枝
枚举左端点,在枚举 >i 的每一个 j
。求两个值，以i为起点的和，与以 i+1
为起点的或和。如果两个值是一样的说明没必要 a[i]
没必要在此区间存在
#include<bits/stdc++.h>
using namespace std;
int a[200005];
set<int>s;
int main() {
int n; cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
int x = a[i], y = 0;
s.insert(x);
for (int j = i + 1; j < n; j++) {
x |= a[j], y |= a[j];
s.insert(x);
if (x == y) //离谱的剪枝
{ break; }
}
}
cout << s.size() << endl;
return 0;
}思路二:st表+贪心.
st表可以求出每个区间的或和.我们枚举点,再枚举每一位 j
,对于点的第 j 位为 i
的点,我们直接记录当前最右的第 j 位为 1 的位置是
i , last[j]=i.如果 i 的第
j 位不为 1 ,那么求 (last[j],i) 之间的或和,用
set 记录.这样是不会漏解的.
相当于把每个点作为右端点 r，找到能使得
(l,r) 间的亦或与 r 的第 j
位相异的最靠右的左端点，即 last[j]。本质是每次的记录
ask(last[j],i) 都是能改变(相异于) a[i]
的。
#include <iostream>
#include <cstring>
#include <set>
#include <cmath>
using namespace std;
const int N = 100010,M = 21;
int a[N],n,last[M],f[N][M];
set<int> s;
void init()
{//st表预处理与的区间和.
for(int j=0;j<M;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
if(!j) f[i][j] = a[i];
else f[i][j] = f[i][j-1]|f[i+(1<<j-1)][j-1];
}
int ask(int l,int r)
{
if(!l) return -1;
int len = r-l+1;
int k = log(len)/log(2);
return f[l][k]|f[r-(1<<k)+1][k];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
init();
for(int i=1;i<=n;i++)
{
s.insert(a[i]);
for(int j=0;j<M;j++)
{
if(a[i]>>j&1) last[j] = i;
else s.insert(ask(last[j],i));
}
}
s.erase(-1);
printf("%d\n",s.size());
return 0;
}
D - CodeForces 864C 校车 √
其实是用省略重复情况的模拟，经常遇到，但是我经常被卡很久，因为各种细节考虑情况。
题面： 一辆校车的路线是在坐标轴上的 0 点到 a 点之间往返，每消耗一升汽油能行驶一个单位长度。油箱容量为 b ，在 0 点和 a 点之间有一个加油站，位置是 f 点，在加油站，校车能把油加满。校车从 0 点出发，出发时油是满的。我们称校车从 0 点到 a 点或者从 a 点到 0 点为一趟，请问要进行 k 趟，校车最少要加几次油。
将 0 - a 的 k 次往返的路径展开为一条轴，则题目变成小车从 0 驶向 k·a 的单项行驶，再考虑加油站与油箱最大容积的问题。每次 while 循环为当前点加满油驶向下一个最远的加油站的计算，若移动后位置不变，则为无法驶向下一个加油站，若情况满足直接输出“无解”；还要考虑是否为起步，是否已经为第 k 趟，能否直接到达终点。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int sum=0,flag=1;char c;
for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag=-1;
for(;c<='9'&&c>='0';c=getchar()) sum=(sum<<3)+(sum<<1)+c-'0';
return flag*sum;
}
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
const int MAXN = 32767*2+100;
const int INF = 0x3f3f3f3f;
int main(){
int a,b,f,k;
cin>>a>>b>>f>>k;
int x=f,y=a-f;
if(b<x){
cout<<-1;
return 0;
}
int l,r,o,m;
r=k;l=1;
o=b-x;
m=0;
int xy=2*x+2*y;
int ans=0;
int mm=1;
//cout<<x<<" "<<y<<endl;
while(l<=r){
if(l==r){
if(o>=(m==0?y:x))
break;
}
int l1=l;
l+=(o/xy)*2;
o=o%xy;
if(m==0){
if(o>=2*y){
l++;
m=1;
o-=2*y;
}
}else{
if(o>=2*x){
l++;
m=0;
o-=2*x;
}
}
//cout<<o<<endl;
if(l==r){
if(o>=(m==0?y:x))
break;
}
if(l>r) break;
o=b;
ans++;
if(l==l1&&mm!=1){
ans=-1;
break;
}
mm=0;
//cout<<l<<":"<<ans<<" "<<m<<endl;
}
cout<<ans;
}
/*
*/E - CodeForces 753A 送给你的新年礼物 √
签到题，构造红包数最多的情况
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int sum=0,flag=1;char c;
for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag=-1;
for(;c<='9'&&c>='0';c=getchar()) sum=(sum<<3)+(sum<<1)+c-'0';
return flag*sum;
}
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
const int MAXN = 32767*2+100;
const int INF = 0x3f3f3f3f;
int main(){
int n=read();
int k=1;
for(k=1;n-k>=0;k++){
n-=k;
}
k--;
cout<<k<<endl;
FOR(i,1,k-1)
cout<<i<<" ";
cout<<k+n;
return 0;
}
/*
*/F - CodeForces 923A 升级 ×
一个数论
【题解】
考虑怎么得到数字x2=N,假设是质数p的倍数 那么x1肯定在x2-p+1~x2这个范围内才行 因为p的倍数要刚好大于等于x1, 所以x1肯定是在这两个倍数之间才行 结果已经很显然了 肯定让p的值越大越好。 这样得到的x1才可能越小。 枚举x1在x2-p+1~x2之间。 用同样的方式得到x0就好。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int n;
int x0,x1,x2;
int maxfac(int x){
int j = x;
for (int i = 2;i*i<=x;i++){
if (x%i==0){
while (x%i==0){
x/=i;
}
j = i;
}
}
if (x>1) j = x;
return j;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> x2;
int p = x2-maxfac(x2)+1;
int ans = x2;
for (int x1 = p;x1 <= x2;x1++){
int temp = maxfac(x1);
if (temp!=x1){
x0 = x1-temp+1;
ans = min(ans,x0);
}
}
cout<<ans<<endl;
return 0;
}
#include <cstdio>
using namespace std;
const int maxn = 1e6+10;
int n,ans;
int f[maxn];
inline int Min(int x, int y) {return x<y?x:y; }
int main(){
scanf("%d",&n);
ans = n;
for (int i=2; i<=n; i++) {
if (!f[i]) {
for (int j=2*i; j<=n; j+=i) f[j] = i;
}
f[i] = i-f[i]+1;
}
for (int i=f[n]; i<=n; i++) ans = Min(ans,f[i]);
printf("%d\n",ans);
return 0;
}G - CodeForces 961D 贯穿 √
题目复述： 对于二维坐标系上的给出的一系列点，是否能用两条直线涵盖所有点。（n<100000）
解题思路： 我们假设题目成立，在条件成立的情况下，尝试找到这两条直线。对于这一系列点的任意三个点，三个点表示的三条直线中一定有一条为两条直线中的一条。即，对次三条线各做一次尝试，若被第一条线排除后的点能被另一条线贯穿则题目成立。三条线都不满足则题目不成立。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn = 1e5+5;
const double pi = acos(-1.0);
const ll inf = 0x3f3f3f3f;
ll n;
struct node
{
ll x, y;
}pre[maxn];
bool vis[maxn];
bool kkk(node a, node b, node c){//注意不能用除法
ll k1 = (b.y-a.y)*(c.x-a.x);
ll k2 = (c.y-a.y)*(b.x-a.x);
return k1==k2?true:false;
}
bool check(ll a, ll b){
memset(vis, false, sizeof(vis));
vis[a] = vis[b] = true;
for(ll i = 1; i <= n; i++){
if (i == a || i == b) continue;
if (kkk(pre[a], pre[b], pre[i])) vis[i] = true;
}
ll p1=-1, p2=-1;
for(ll i = 1; i <= n; i++){
if (!vis[i]){
if(p1 == -1) {p1=i;}
else if (p2==-1){p2=i;}
}
}
if (p1==-1||p2==-1) return true;
for(ll i = 1; i <= n; i++){
if (i == p1 || i == p2) continue;
if (!vis[i] && !kkk(pre[p1], pre[p2], pre[i])) return false;
}
return true;
}
int main() {
cin >> n;
for(ll i = 1; i <= n; i++){
cin>>pre[i].x>>pre[i].y;
}
if (n < 5 || check(1, 2) || check(1, 3) || check(2, 3)){
printf("YES\n");
}else printf("NO\n");
return 0;
}H - CodeForces 733D 球球人 √
题目复述： 对于 n 个长方体，输出能使得单个或两个长方体拼合的新长方体的最短棱长最长的情况。（n<100000）
我最开始以为可以无数个长方体拼在一起，就放了，后来才发现只能两个或一个。
解题思路：
考虑单个：直接一边读入，一边记录长方体的最短棱长的最长值和长方体对应编号
考虑两个：两个长方体能拼合当且仅当两个长方体各有两条棱长对应相等，而为了使得拼合后超越单个的情况，拼合的两个长方体一定是补短，即拼合的面是最长棱和第二长棱构成的面。考虑时间复杂度不能两两匹配尝试，考虑将最长棱和第二长棱相同的长方体聚集在一起，考虑以第二棱长、第一棱长、第三棱长的优先级排序 O(nlogn) ，再线性的扫描一遍，因为能拼合的一定相邻，最大的情况只可能为第二棱长、第一棱长相同的，且第三棱长在此基础上最长的两个，一定相邻。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int sum=0,flag=1;char c;
for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag=-1;
for(;c<='9'&&c>='0';c=getchar()) sum=(sum<<3)+(sum<<1)+c-'0';
return flag*sum;
}
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
const int maxn = 100000+100;
struct node{
int a,b,c;int k;
void sor(){
if(a>b) swap(a,b);
if(b>c) swap(b,c);
if(a>b) swap(a,b);
}
}x[maxn];
inline bool cmp(node e1,node e2){
if(e1.b!=e2.b) return e1.b>e2.b;
if(e1.c!=e2.c) return e1.c>e2.c;
return e1.a>e2.a;
}
int main(){
int n=read();
int ma=0;int p=0,q=0;
FOR(i,1,n){
cin>>x[i].a>>x[i].b>>x[i].c;
x[i].k=i;
x[i].sor();
if(x[i].a>ma){
ma=x[i].a;
p=i;
}
}
sort(x+1,x+1+n,cmp);
FOR(i,1,n-1){
if(x[i].b<=ma) continue;
if(x[i].b==x[i+1].b&&x[i].c==x[i+1].c){
if(x[i].a+x[i+1].a>ma){
ma=x[i].a+x[i+1].a;
p=x[i].k;
q=x[i+1].k;
}
}
}
if(q){
cout<<2<<endl;
cout<<p<<" "<<q;
}else{
cout<<1<<endl;
cout<<p;
}
}
/*
*/I - CodeForces 687C 经验书
题意： 给你n个数，然后让这些数相加组合，然后在这些组合的数里可以再相加组合搞出给定 k，输出这些组合的数。
思路： DP。 dp[i][j]
代表数值为i时值为j能否被构成那么如果dp[i][j]能被构成那么
dp[i+x][j] dp[i+x][j+x]
都能被构成，这样状态转移方程就出来了
在枚举到第i个coin的时，dp[i][j],i
肯定能被a[i]组合，
然后再枚举<=a[i]的部分，dp[i][j]的具体意义就是在coin值是i的时候，能用j去组合。
为了防止重复利用coin，从j枚举到a[i];
最后dp[k][h]==1的把h塞到容器里去，最后输出。
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int qq = 505;
int dp[qq][qq]; //代表当数值为i的时候，j数字能否被构成
int num[qq];
int main(){
int n,k;cin >> n >> k;
dp[0][0] = 1;
for(int l=0; l<n; ++l){
int x; cin >> x;
for(int i=k; i>=x; --i)
for(int j=0; j<=k-x; ++j)
if(dp[i-x][j]) dp[i][j] = dp[i][j+x] = 1;
}
int tot=0;
for(int i=0; i<=k; ++i)
if(dp[k][i]) num[tot++] = i;
cout << tot << endl;
for(int i=0; i<tot; ++i)
cout << num[i] << " ";
cout << endl;
return 0;
}