ZJNU-2020-12-11
A-Array
B-Building Blocks
C-Cats
题意：
构造一个长度为n的数组。任意两只拥有相同高度的猫不能住在相邻的猫舍，并且他们之间的的猫的最小高度不能这两只相同高度的猫。
solution：
1
2 1 2
3 2 3 1 3 2 3
这样构造下去。
D-Delete Prime
题意：
给定一个长度为n的数组。
每伦将1和素数位置的数取出放到另一个数组中。然后将剩下的下标改变，但数字不变，继续取1和素数位置的数取出的操作。
问
1 n k，求值为k的下标
2 n k，求新的数组下表为k的值
solution：
将1e6的数的1和素数位置分批次取出，然后二分求取。
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int prime[1000005],cnt=0;
int vis[1000005];
vector<int> e[100000];
set<int>st;
int t;
int main()
{
prime[cnt++]=1;
st.insert(1);
for(int i=2;i<=1000000;i++)
{
st.insert(i);
if(!vis[i])
{
prime[cnt++]=i;
for(int j=i;j<=1000000;j+=i)
vis[j]=1;
}
}
int c=0;
while(st.size()>0)
{
int i=0,cc=1;
for(set<int>::iterator it=st.begin();it!=st.end();it++)
{
if(cc==prime[i])
{
e[c].push_back(*it);
i++;
}
cc++;
}
i=0;
while(i<e[c].size())
{
st.erase(st.find(e[c][i]));
i++;
}
e[c].push_back(INF);
c++;
}
scanf("%d",&t);
while(t--)
{
int op,n,k;
scanf("%d%d%d",&op,&n,&k);
if(op==1)
{
int res=0;
for(int i=0;i<c;i++)
{
int pos=lower_bound(e[i].begin(),e[i].end(),k)-e[i].begin();
if(e[i][pos]==k)
{
printf("%d\n",res+pos+1);
break;
}
pos=lower_bound(e[i].begin(),e[i].end(),n)-e[i].begin();
if(e[i][pos]>n)pos--;
res+=pos+1;
}
}
else if(op==2)
{
for(int i=0;i<c;i++)
{
int pos=lower_bound(e[i].begin(),e[i].end(),n)-e[i].begin();
if(e[i][pos]>n)pos--;
if(pos+1>=k)
{
printf("%d\n",e[i][k-1]);
break;
}
k=k-pos-1;
}
}
}
return 0;
}
E-Eliminate the Virus
F-Flee from Maze
G-Grid Coloring
H-Happy Morse Code
题意：
给定字母的二进制编码，求构造出二进制串s的二进制编码有几种不同的方法。
solution：
dp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int t,n,m;
string s;
int dp[500005];
int flag[500005];
string ss[30],ch[30];
bool check(int pos,int now)
{
if(pos<ss[now].length()-1)return false;
for(int i=0;i<ss[now].length();i++)
if(ss[now][i]!=s[pos+i-ss[now].length()+1])return false;
return true;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
cin>>ch[i]>>ss[i];
for(int i=0;i<=n;i++)dp[i]=0,flag[i]=0;
cin>>s;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(check(i,j))
{
if(ss[j].length()-i==1)
{
dp[i]+=1;
if(flag[i]==0)
flag[i]=1;
else if(flag[i]==1)
flag[i]=2;
}
else if(ss[j].length()<=i)
{
dp[i]=(dp[i-ss[j].length()]+dp[i])%128;
if(flag[i-ss[j].length()]==1)
{
if(flag[i]==0)
flag[i]=1;
else if(flag[i]==1)
flag[i]=2;
}
else if(flag[i-ss[j].length()]==2)
flag[i]=2;
}
}
}
}
if(flag[n-1]==0)
printf("nonono\n");
else if(flag[n-1]==1)
printf("happymorsecode\n");
else
printf("puppymousecat %d\n",dp[n-1]);
}
return 0;
}
I-Intersections
题意：
给定能向左向右走的条件，以及花费，向上向下走的条件，以及花费。求从起点到终点的最短距离。
solution：
另类最短路Dijktra（）
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int n,m,sx,sy,tx,ty;
int a[505][505];
int b[505][505];
int c[505][505];
int w[505][505];
ll t[505][505];
int dx[]={
1,-1,0,0},dy[]={
0,0,1,-1};
struct node
{
int x,y;
ll t;
bool operator>(const node p)const
{
return t>p.t;
}
};
void dijktra()
{
memset(t,INF,sizeof(t));
t[sx][sy]=0;
priority_queue<node,vector<node>,greater<node>>que;
que.push(node{
sx,sy,t[sx][sy]});
while(!que.empty())
{
node p=que.top();que.pop();
if(p.t%(a[p.x][p.y]+b[p.x][p.y])<a[p.x][p.y])
{
for(int i=0;i<2;i++)
{
int x=p.x+dx[i],y=p.y+dy[i];
if(x<0||x>=n||y<0||y>=m)continue;
ll tt=p.t;
if(i==0)
tt+=w[p.x][p.y];
else
tt+=w[x][y];
if(tt>=t[x][y])continue;
t[x][y]=tt;
que.push(node{
x,y,tt});
}
}
else
{
ll tem=a[p.x][p.y]+b[p.x][p.y]-(p.t%(a[p.x][p.y]+b[p.x][p.y]));
for(int i=0;i<2;i++)
{
int x=p.x+dx[i],y=p.y+dy[i];
if(x<0||x>=n||y<0||y>=m)continue;
ll tt=p.t+tem;
if(i==0)
tt+=w[p.x][p.y];
else
tt+=w[x][y];
if(tt>=t[x][y])continue;
t[x][y]=tt;
que.push(node{
x,y,tt});
}
}
if(p.t%(a[p.x][p.y]+b[p.x][p.y])!=0&&p.t%(a[p.x][p.y]+b[p.x][p.y])>=a[p.x][p.y])
{
for(int i=2;i<4;i++)
{
int x=p.x+dx[i],y=p.y+dy[i];
if(x<0||x>=n||y<0||y>=m)continue;
ll tt=p.t;
if(i==2)
tt+=c[p.x][p.y];
else
tt+=c[x][y];
if(tt>=t[x][y])continue;
t[x][y]=tt;
que.push(node{
x,y,tt});
}
}
else
{
ll tem=0;
if(p.t%(a[p.x][p.y]+b[p.x][p.y])==0)
tem=a[p.x][p.y];
else
tem=a[p.x][p.y]-p.t%(a[p.x][p.y]+b[p.x][p.y]);
for(int i=2;i<4;i++)
{
int x=p.x+dx[i],y=p.y+dy[i];
if(x<0||x>=n||y<0||y>=m)continue;
ll tt=p.t+tem;
if(i==2)
tt+=c[p.x][p.y];
else
tt+=c[x][y];
if(tt>=t[x][y])continue;
t[x][y]=tt;
que.push(node{
x,y,tt});
}
}
}
}
int main()
{
scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&tx,&ty);
sx--;sy--;tx--;ty--;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&a[i][j]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&b[i][j]);
for(int i=0;i<n;i++)
for(int j=0;j<m-1;j++)
scanf("%d",&c[i][j]);
for(int i=0;i<n-1;i++)
for(int j=0;j<m;j++)
scanf("%d",&w[i][j]);
dijktra();
printf("%lld",t[tx][ty]);
return 0;
}
J-Just Multiplicative Inverse
题意：
求操作次数的期望。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int t;
ll vis[1000005];
int main()
{
scanf("%d",&t);
vis[0]=vis[1]=1;
while(t--)
{
int p;scanf("%d",&p);
ll res=1;
for(int i=2;i<p;i++)
{
vis[i]=vis[p%i]+1;
res=res+vis[i];
}
printf("%.9f\n",res*1.0/(p-1));
}
return 0;
}
