2020 Jiangsu Collegiate Programming Contest（C,D,H,I,J）

oj: CodeForces

2021/2/27 组队赛

C. Cats

oj: CodeForces

题意

让你求出满足条件的任意一个序列并输出。
条件：两个相等的值之间至少存在一个小于这个值的其他值。
eg: { 1 , 2 , 3 } \{1,2,3\} {1,2,3}符合条件， { 3 , 4 , 3 } \{3,4,3\} {3,4,3}不符合条件。

题解

首先肯定只能有一个$1$，我们假设这个$1$在最左边。
然后考虑$2$的位置，$2$只能在$1$的右边。
$3$只能在$2$的两边，之后的类比$3$的情况。
构造出来的序列就是这样的：
{ 1 } \{1\} {1}
{ 1 , 2 } \{1,2\} {1,2}
{ 1 , 3 , 2 , 3 } \{1,3,2,3\} {1,3,2,3}
{ 1 , 4 , 3 , 4 , 2 , 4 , 3 , 4 } \{1,4,3,4,2,4,3,4\} {1,4,3,4,2,4,3,4}
{ 1 , 5 , 4 , 5 , 3 , 5 , 4 , 5 , 2 , 5 , 4 , 5 , 3 , 5 , 4 , 5 } \{1,5,4,5,3,5,4,5,2,5,4,5,3,5,4,5\} {1,5,4,5,3,5,4,5,2,5,4,5,3,5,4,5}
我们找规律发现，每增加一个数$i$可以增加$2^{i-2}$个位置，肯定可以找到满足最大长度$100000$的序列（等比数列前$n$项和可以证明）。
对于$n$不是$2$的幂次的情况，我们可以找到比$n$大的最小的$2$的幂次构造出来的数组，输出前$n$项即可。
剩下就是模拟构造出来这个数组的过程了。
这里假设数组中最大的那个数是$num$。
可以发现每个$num$间距为$2$,每个$num-1$间距为$4$,每个$num-2$间距为$8$，因此我们求出$num$，倒序枚举要放的数和开始放这个的数的起始位置，并同时维护间距即可。
注意$1$和$2$的特殊情况。

代码

#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;
}
inline int read(){int s=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}return s*f;
}
const int N = 1e6+7;
int a[N];
void solve(){int n=read();if(n==1){puts("1");return ;}int num=0;while((1<<num)<n) num++;int nn=num+1;rp(i,1,(1<<num)) a[i]=0;// outval3(n,num,nn);a[1]=1;int delta=2;while(delta<=(1<<num)){int id=0;rp(i,1,(1<<num)){if(!a[i]){id=i;break;}}if(!id) break;while(id<=(1<<num)){a[id]=nn;id+=delta;}nn--;delta*=2;}rp(i,1,n) cout<<a[i]<<(i==n?"\n":" ");
}
int main(){//ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#elsefreopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// debug = 1;
#endiftime_t beg, end;if(debug) beg = clock();int T=1;while(T--) solve();if(debug) {end = clock();printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);}return 0;
}

D. Delete Prime

oj: CodeForces

题意

定义一个生成序列的流程：

1. 根据 $n$ 生成一个 $1,2,...,n$ 数组。
2. 取出序列里第 $1$ 和第素数位置的元素，保持其相对位置不变加入到 $D$ 数组的末尾。
3. 重复 $2$ 过程直到原数组为空。

例如 $n=6$ 时，数组 $D$ 为 $[1,2,3,5,4,6]$ 。

有若干次提问，每次提问会给出 $3$ 个整数： $t,n,k$ 。其中 $t$ 表示提问类型：

1. 给定 $n$ 和 $k$ ，求出 $x$ 满足 $D[x]=k$ 。
2. 给定 $n$ 和 $k$ ，求出 $x$ 满足 $D[k]=x$ 。

题解

测试了一下， $n$ 为 $1000,000$ 时，需要 $80$ 轮迭代求出 $D$ 。把每次迭代取出的数单独存为一个数组，那么这些数组都是有序的。

然后根据给定的 $n$ 和 $k$ 从第一个数组到最后一个数组依次二分查找即可。

1. 给定了值，求索引。按照迭代顺序依次枚举数组，直接在此数组里二分查找 $k$ ，如果找不到就维护一个 和，和 保存的是此数组中小于等于 $n$ 的数的个数。如果找到了，就把 $k$ 在此数组中的位置加上维护的 和 就是 $k$ 在 $D$ 数组中的位置。
2. 给定了位置，求值。仿照情况 $1$ 的思路，维护一个 和 保存小于等于 $n$ 的元素的个数，一旦个数之和大于等于 $k$ ，就说明 $D$ 中第 $k$ 个元素在当前我们枚举的数组里。直接输出即可。

代码

#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const int maxn = 1000000;inline LL read() {LL x(0), f(1); char ch(getchar());while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }return x * f;
}int a[maxn + 1];
int used[maxn + 1];
vector<int> b[81];
int cnt;vector<int> arr;
int vis[1000006];
void doit(int maxnum) {for(int i = 2; i <= maxnum; ++i) {if(!vis[i]) arr.push_back(i);for(int j = 0; j < arr.size() && arr[j] * i <= maxnum; ++j) {vis[arr[j] * i] = 1;if(i % arr[j] == 0) break;}}
}int findl(int de, int val) {return lower_bound(b[de].begin(), b[de].end(), val) - b[de].begin();
}int findu(int de, int val) {return upper_bound(b[de].begin(), b[de].end(), val) - b[de].begin();
}void sol() {int t = read(), n = read(), k = read();if(t == 1) {int num = 0;_for(i, cnt) {int p = findl(i, k);if(p < b[i].size() && b[i][p] == k) {printf("%d\n", num + p + 1);return;}else num += findu(i, n);}}else {_for(i, cnt) {int p = findu(i, n);if(p >= k) {printf("%d\n", b[i][k - 1]);return;}else k -= p;}}
}int main() {doit(1000000);_rep(i, 1, maxn) a[i] = i;cnt = 0;int n = 1000000;while(n) {_rep(i, 1, n) used[i] = 0;used[1] = 1;b[cnt].push_back(a[1]);for(int i = 0; i < arr.size() && arr[i] <= n; ++i) {used[arr[i]] = 1;b[cnt].push_back(a[arr[i]]);}int tn = 0;_rep(i, 1, n) if(!used[i]) a[++tn] = a[i];n = tn;++cnt;}int T = read();_for(i, T) {sol();}return 0;
}

H. Happy Morse Code

oj: CodeForces

题意

给定一组密钥 $s$ 和一串密码 $t$ ，求出是否可以根据这组密钥唯一求解密码，如果不能求解就输出nonono，如果能唯一求解就输出happymorsecode，如果有多种求解方式就输出puppymousecat和求解方法数，答案对 $128$ 取余。

题解

动态规划。

定义 $dp[i]$ 为密码的字串 $t[i:n]$ 的求解方法数。
$ln[j]$ 为第 $j$ 个密钥的长度。

边界值： $dp[n]=1$

状态转移：$dp[i]=\sum _{j=0}^{m-1}dp[i+ln[j]]$ $(t[i:i+len(s[j])]=s[j])$。

注意，我们需要根据 $dp[0]$ 的值来判断答案有多少种求解方式，所以 $i$ 中间的计算过程不能直接对 $128$ 取余，否则我们不知道最后的答案 $0$ 是因为没有解还是取余后变成了 $0$ 。所以稳妥的做法是如果大于 $128$ 就先减去 $128$ ，再对 $128$ 取余，再加上 $128$ 。之后答案的值就能维持在大于 $128$ 但不超过 $256$ 的水平。最后输出的时候再对 $128$ 取余。

代码

#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const int maxn = 100005;inline LL read() {LL x(0), f(1); char ch(getchar());while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }return x * f;
}LL dp[maxn];
int n, m;
char s[26][11];
char t[maxn];
int ln[maxn];
int fl;void init() {fl = 0;_for(i, n + 1) dp[i] = 0;
}int che(int i, int p) {_for(j, ln[i]) {if(t[p + j] != s[i][j]) return 0;}return 1;
}void sol() {init();_for(i, m) {scanf("%s", s[i]);scanf("%s", s[i]);ln[i] = strlen(s[i]);}scanf("%s", t);dp[n] = 1;for(int i = n - 1; i >= 0; --i) {_for(j, m) {if(i + ln[j] > n) continue;if(che(j, i)) {dp[i] += dp[i + ln[j]];if(dp[i] > 128) {dp[i] = (dp[i] - 128) % 128 + 128;}}}}if(dp[0] == 0) printf("nonono\n");else if(dp[0] == 1) printf("happymorsecode\n");else printf("puppymousecat %lld\n", dp[0] % 128);
}int main() {int T = read();_for(i, T) {n = read(), m = read();sol();}return 0;
}

I. Intersections

oj: CodeForces

题意

题意有点难懂，其实就是让你求出从开始坐标到结束坐标的最短时间。
不过有个限制条件：
假设当前位置坐标为$(i,j)$。
如果当前时间$t$%$(a[i][j]+b[i][j])$小于$a[i][j]$：
当$i>1$时，可以往下走，花费时间为$w[i-1][j]$。
当$i<n$时，可以往上走，花费时间为$w[i][j]$。
否则：
当$j>1$时，可以往左走，花费时间为$c[i-1][j]$。
当$j<m$时，可以往右走，花费时间为$c[i][j]$。

题解

比赛时题意没读懂，读懂后相对而言就好做了。
第一想法是$dp$进行维护，但是可能有一种情况就是绕一圈走的比直接走的快，这样$dp$的方向就不确定了，没办法维护。
因此我们可以考虑最短路的做法，每次取时间最短的点进行松弛，维护当前点到起始点的最短时间即可。

代码

#include<bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define debug puts("ac")
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){int s=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}return s*f;
}
struct node{int x,y;ll w;bool operator <(const node& others)const {return w>others.w;}
};
int a[507][507],b[507][507],w[507][507],c[507][507];
ll dis[507][507];
int sx,sy,ex,ey;
int n,m;
int vis[507][507];
void Dijkstra(){priority_queue<node> q;q.push(node{sx,sy,0});dis[sx][sy]=0;while(!q.empty()){node t=q.top();q.pop();int x=t.x,y=t.y;if(vis[x][y]) continue;vis[x][y]=1;ll temp1=t.w%(a[x][y]+b[x][y]);ll temp2=a[x][y]+b[x][y]-temp1;if(x>1){if(temp1<a[x][y]){//可以直接从(x,y)到(x-1,y)if(dis[x-1][y]>dis[x][y]+w[x-1][y]){dis[x-1][y]=dis[x][y]+w[x-1][y];q.push(node{x-1,y,dis[x-1][y]});}}else{//不可以的话，可以等到满足条件在走if(dis[x-1][y]>dis[x][y]+w[x-1][y]+temp2){dis[x-1][y]=dis[x][y]+w[x-1][y]+temp2;q.push(node{x-1,y,dis[x-1][y]});}}}if(x<n){if(temp1<a[x][y]){if(dis[x+1][y]>dis[x][y]+w[x][y]){dis[x+1][y]=dis[x][y]+w[x][y];q.push(node{x+1,y,dis[x+1][y]});}}else{if(dis[x+1][y]>dis[x][y]+w[x][y]+temp2){dis[x+1][y]=dis[x][y]+w[x][y]+temp2;q.push(node{x+1,y,dis[x+1][y]});}}}if(y>1){if(temp1<a[x][y]){temp2=a[x][y]-temp1;if(dis[x][y-1]>=dis[x][y]+c[x][y-1]+temp2){dis[x][y-1]=dis[x][y]+c[x][y-1]+temp2;q.push(node{x,y-1,dis[x][y-1]});}}else{if(dis[x][y-1]>dis[x][y]+c[x][y-1]){dis[x][y-1]=dis[x][y]+c[x][y-1];q.push(node{x,y-1,dis[x][y-1]});}}}if(y<m){if(temp1<a[x][y]){temp2=a[x][y]-temp1;if(dis[x][y+1]>=dis[x][y]+c[x][y]+temp2){dis[x][y+1]=dis[x][y]+c[x][y]+temp2;q.push(node{x,y+1,dis[x][y+1]});}}else{if(dis[x][y+1]>dis[x][y]+c[x][y]){dis[x][y+1]=dis[x][y]+c[x][y];q.push(node{x,y+1,dis[x][y+1]});}}}}cout<<dis[ex][ey]<<endl;
}
void solve(){n=read(),m=read(),sx=read(),sy=read(),ex=read(),ey=read();rp(i,1,n) rp(j,1,m) a[i][j]=read();rp(i,1,n) rp(j,1,m) b[i][j]=read();rp(i,1,n) rp(j,1,m-1) c[i][j]=read();rp(i,1,n-1) rp(j,1,m) w[i][j]=read();mst(dis,0x3f);Dijkstra();
}
int main(){//ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#elsefreopen("in.txt", "r", stdin);//debug = 1;
#endif//time_t beg, end;//if(debug) beg = clock();int T=1;while(T--) solve();/*if(debug) {end = clock();printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);}*/return 0;
}

J. Just Multiplicative Inverse

oj: CodeForces

题意

给定一个函数，每回合给出一个 $p$ ，求出此函数的调用次数。

题解

观察后发现函数再调用过程中 $p$ 不变， $x$ 持续变小。所以可以按 $x$ 从小到大计算，较大的 $x$ 可以利用到较小的 $x$ 的结果，从而避免多余计算，进行记忆化搜索。

代码

#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const int maxn = 1000005;inline LL read() {LL x(0), f(1); char ch(getchar());while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }return x * f;
}
LL p, ans;
LL dp[maxn];
inline LL dfs(LL x, LL p, int dep) {if(dp[x] != -1) return dp[x];if(x <= 1) return 1;return dp[x] = dfs(p % x, p, dep + 1) + 1;
}
void init() {ans = 0;_rep(i, 1, p) dp[i] = -1;
}
void sol() {init();_rep(i, 1, p - 1) ans += dfs(i, p, 1);
}
int main() {int T = read();_for(i, T) {p = read();sol();printf("%.10f\n", 1.0 * ans / (p - 1));}return 0;
}