链接
题意：
给定 $M$ 个城市，每年会选出一个城市举办比赛，现给出前 $N$年城市举办比赛的情况。在接下来的年份中，每年的比赛会在举办比赛次数最小的城市举办，如果有很多城市举办次数均为最小值，则在编号最小的城市举办比赛。现给出 $Q$ 个询问，每次询问第 $K$ 年在哪个城市举办比赛。 $N+1 \le K \le 1e18, 1\le M,N,Q \le 5e5$
分析：
首先我们能想到将其前n个填充到一个这$m$个里面，找到最高点然后高度乘以m，如果超过这个数答案就是，(k-1)%m+1，那如果在这个数之内那？
我们知道我们填充数的时候，先找最矮的，就是出现次数最少的，之后，一样找编号小的，那么我们可以先那前n个提取出来，然后将其前空的个数算出来，之后就可以直接算了。
ll n,m,q;
ll a[maxn],c[maxn];
void solve()
{
scanf("%lld%lld%lld",&n,&m,&q);
for(int i=1;i<=n;i++){
ll k;
scanf("%lld",&k);
a[i]=(c[k]++)*m+k;
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) a[i]-=i;
while(q--){
ll k;
scanf("%lld",&k);
k+=lower_bound(a+1,a+n+1,k-n)-a-1-n;
printf("%lld\n",(k-1)%m+1);
}
}
A - Blood Pressure
正常求即可
B - Cycle Hit
两层for判断有没有重复的
C - chokudai
动态转移：出现第一个字符++，后面没出现一个字符加上前一字符的数量。 别忘了$mod\ 1e9+7$
D - Number of Shortest paths
最短路来做，遇到等于当前最短路的 加上有这条路径来的最短路径。1-2 1-3 1-4 2-5 3-5 4-5 5-6 5- 7 5-8 6-9 7-9 8-9
成这样形状，可知到达5的最短路径的种数一共3种 5-6那也是3种同理5-7 三种 5-8 三种
那么从6 ，7，8到9，路径长度都一样切都是最短的，那么把这三条路径上过来的种数求和即可，注意标记点走过的和已入队列的就不要在入队列了。
ll n,m;
vector <ll> v[maxn];
ll cnt[maxn],dis[maxn],vis[maxn];
void dfs(){
queue<ll> q;
q.push(1);
cnt[1]=1;
dis[1]=0;
vis[1]=1;
while(!q.empty()){
ll top=q.front();
q.pop();
for(int i=0;i<(int)v[top].size();i++){
ll u=v[top][i];
if(dis[u]==dis[top]+1){
cnt[u]=(cnt[u]+cnt[top])%mod;
if(!vis[u]) q.push(u),vis[u]=1;
}else if(dis[u]>dis[top]+1){
dis[u]=dis[top]+1;
cnt[u]=cnt[top];
if(!vis[u]) q.push(u),vis[u]=1;
}
}
}
}
void solve()
{
memset(dis,0x3f,sizeof dis);
cin>>n>>m;
for(int i=1;i<=m;i++){
ll a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs();
cout<<cnt[n]<<endl;
}
E - Red Polyomino
注意数据范围为8*8所以我们可以直接暴搜，但是需要标记，我们可以用int128 ,当然也可以用组合string的方法，我记得好像也可以用vector来维护。上面说的这三种都是用map来标记。
性质还是都一样的。但是如果来个更大的__int128 可能就不能够维护了。这个其实是64位维护还行。蓝桥杯记得有一道map维护string 维护状态。
///string
map<string,bool>mp;
ll a[100];
ll ans,n,k;
ll dp[10][10];
void get(ll pos, ll &x, ll &y) {
pos -= 1;
x = pos / n + 1;
y = pos % n + 1;
}
void dfs(ll cnt){
if(cnt==k) {
ans++;
return ;
}
for(ll i=1;i<=n*n;i++){
ll x,y;
get(i,x,y);
if(dp[x][y] == 2 ||dp[x][y]==1)continue;
bool flag = false;
for(ll j=1;j<=4;j++){
ll fx=dx[j]+x;
ll fy=dy[j]+y;
if(fx>=1&&fx<=n&&fy>=1&&fy<=n&&dp[fx][fy]==2) flag=true;
}
if(flag || cnt ==0 ){
ll b[100];
for(int j=0;j<=64;j++){
b[j]=a[j];
}
a[i] |= 1;
string s="";
for(int j=0;j<=64;j++){
s+=char(a[j]);
}
if(mp[s]) {
for(int j=0;j<=64;j++) a[j]=b[j];
}
else {
mp[s]=1;
dp[x][y]=2;
dfs(cnt+1);
dp[x][y]=0;
for(int j=0;j<=64;j++) a[j]=b[j];
}
}
}
}
void solve()
{
ios::sync_with_stdio(false);
string s;
cin >> n >> k;
ans = 0;
for (int i = 1; i <= n; i++) {
cin >> s;
for (int j = 0; j < n; j++) {
if (s[j] == '#') {
dp[i][j + 1] = 1;
}
if (s[j] == '.') {
dp[i][j + 1] = 0;
}
}
}
dfs(0);
cout<<ans<<endl;
}
///__int128
unordered_map<__int128,bool>mp;
ll ans,n,k;
ll dp[10][10];
void get(ll pos, ll &x, ll &y) {
pos -= 1;
x = pos / n + 1;
y = pos % n + 1;
}
void dfs(ll cnt,__int128 num){
if(cnt==k) {
ans++;
return ;
}
for(ll i=1;i<=n*n;i++){
ll x,y;
get(i,x,y);
if(dp[x][y] == 2 ||dp[x][y]==1)continue;
bool flag = false;
for(ll j=1;j<=4;j++){
ll fx=dx[j]+x;
ll fy=dy[j]+y;
if(fx>=1&&fx<=n&&fy>=1&&fy<=n&&dp[fx][fy]==2) flag=true;
}
if(flag || cnt ==0 ){
__int128 num1=num;
num1 |=((__int128)1<<i);
if(mp[num1]) continue;
mp[num1]=1;
dp[x][y]=2;
dfs(cnt+1,num1);
dp[x][y]=0;
}
}
}
void solve()
{
ios::sync_with_stdio(false);
string s;
cin >> n >> k;
ans = 0;
for (int i = 1; i <= n; i++) {
cin >> s;
for (int j = 0; j < n; j++) {
if (s[j] == '#') {
dp[i][j + 1] = 1;
}
if (s[j] == '.') {
dp[i][j + 1] = 0;
}
}
}
dfs(0,(__int128)0);
cout<<ans<<endl;
}
