12.Last Problem

思路:

以n为中心，它的上下左右分别为a,b,c,d，同时n也是a的下，b的上，c的右，d的左
所以a + c = b + d，令a=1，c=4，则b=2，d=3
然后逆序dfs构造即可

AC Code:

#include<cstdio>
#include<iostream>
#include <cstring>
#include<algorithm>
using namespace std;
// #define TDS_ACM_LOCAL
const int N=2e3+9;
int m[N][N];
void dfs(int x, int y, int v){
    if(v<=0)    return ;
    if(m[x][y+1]!=v-1)    dfs(x,y+1,v-1);
    if(m[x-1][y]!=v-2)    dfs(x-1,y,v-2);
    if(m[x+1][y]!=v-3)    dfs(x+1,y,v-3);
    if(m[x][y-1]!=v-4)    dfs(x,y-1,v-4);
    m[x][y]=v;
    cout<<x<<" "<<y<<" "<<v<<endl;
    return ;
}

void solve(){
    int n;
    cin>>n;
    memset(m, 0, sizeof(m));
    dfs(1000,1000,n);
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

11.Kindergarten Physics

思路:

很难得的没读错题目，同时想到了比萨斜塔实验，觉得d不会改变，并且观察到10^-6的误差在数据范围内似乎可以做（1 ≤ a , b , d , t0 ≤ 100），但是想到前几场觉得没这么简单，就没做了。。。。

直接输出d即可

AC Code:

#include<cstdio>
#include<iostream>
#include <cstring>
#include<algorithm>
using namespace std;
// #define TDS_ACM_LOCAL
void solve(){
    int a, b, d, t;
    cin>>a>>b>>d>>t;
    cout<<d<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

2.Blow up the Enemy

思路:

儿子肯定直接选价值最大的武器（即为最小次数打出100伤害），张三如果不选相同次数即可打出100伤害的武器就会输，所以我们统计武器中最快打出100伤害的武器的个数k，k / 2 即为儿子输的概率，求儿子赢的概念为1 − k / 2

AC Code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const double pi = acos(-1.0);
#define INF 0x3f3f3f3f
// #define TDS_ACM_LOCAL
const int N=1009;
const int hea=100;
int n, time, k, mx;
double x, y, ans;
void solve(){
    int n;
    cin>>n;
    mx=INF;
    for(int i=0; i<n; i++){
        cin>>x>>y;
        time=ceil((hea-x)/x)*y;
        if(time<mx) mx=time, k=1;
        else if(time==mx)   k++;
    }
    ans=1.0-(double)(0.5*k/n);
    cout<<ans<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

5.Equal Sentences

题目大意:

给你一个有n个单词的字符串，求“几乎相等”的字符串序列的个数
对于“几乎相等”的定义为：
1、两个字符串的多重集相等（即单词出现的次数相等）
2、每个单词的第i个在两个序列中出现的位置之差不超过1（暗示互换单词位置）

思路:

因为位置之差不大于1，所以考虑交换相邻的两个单词来构造“几乎相等”（包括其本身）
在交换时，注意相同的单词不能交换，不能连着交换一个单词两次（例a, b, c不能交换成b,c,a）
其中dp[i]为前 i 个单词组成的“几乎相等”字符串的个数，所以dp[0]=dp[1]=1;
相邻两个单词相等，则不交换为dp[i]=dp[i-1];
不等交换，为dp[i]=(dp[i-1]+dp[i-2])%mod;

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const double pi = acos(-1.0);
#define INF 0x3f3f3f3f
// #define TDS_ACM_LOCAL
const int N=1e5 +9;
const int mod=1e9 +7;
int n, dp[N];
string s[N];
void solve(){
    cin>>n;
    dp[0]=dp[1]=1;
    for(int i=1; i<=n; i++){
        cin>>s[i];
        if(i>1){
            if(s[i]==s[i-1])    dp[i]=dp[i-1];
            else dp[i]=(dp[i-1]+dp[i-2])%mod;
        }
    }
    cout<<dp[n]<<endl;
    return ;
}   

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

4.Deliver the Cake

思路:

L和R可以考虑将换手造成的时间消耗放在边权上，对于M可以考虑将M分成L和R两条路（默认优先L）
然后直接跑dijkstra就行，如果起点或者终点为M，需要创建边权为0的虚拟点代替

AC Code:

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
#define P pair<ll,int>
#define INF 0x3f3f3f3f
using namespace std;
const int N=2e5+10, M=2e6+10;

int T,n,m,s,t,x;
int to[M],nxt[M],val[M],head[N],idx;
char c[N];
ll dis[N];
bool st[N];

inline void add(int a,int b,int c)
{
    to[idx]=b,nxt[idx]=head[a],val[idx]=c,head[a]=idx++;
}

void dijkstra()
{
    memset(st,false,sizeof st);
    memset(dis,INF,sizeof dis);
    priority_queue<P,vector<P>,greater<P>> heap;
    if(c[s]=='M') heap.push({0,0}), dis[0]=0;
    else heap.push({0,s}), dis[s]=0;
    
    while(heap.size())
    {
        P t=heap.top();
        heap.pop();
        
        int id=t.second;
        if(st[id]) continue;
        st[id]=true;
        
        for(int i=head[id];~i;i=nxt[i])
        {
            int j=to[i];
            if(dis[j]>dis[id]+val[i])
            {
                dis[j]=dis[id]+val[i];
                heap.push({dis[j],j});
            }
        }
    }
}

void solve(){
    idx=0;
    memset(head,-1,sizeof head);   
        
    scanf("%d%d%d%d%d",&n,&m,&s,&t,&x);
    scanf("%s",c+1);
    if(c[s]=='M')
        add(0,s,0), add(s,0,0), add(0,s+n,0), add(s+n,0,0);
    if(c[t]=='M')
        add(2*n+1,t,0), add(t,2*n+1,0), add(2*n+1,t+n,0), add(t+n,2*n+1,0);
    int u, v, val;
    for(int i=0; i<m; i++){
        cin>>u>>v>>val;
        if(c[u]==c[v] && (c[u]=='R'||c[u]=='L'))
            add(u,v,val), add(v,u,val);
        else if(c[u]==c[v] && c[u]=='M')
            add(u,v,val), add(v,u,val), add(u+n,v,val+x), add(v,u+n,val+x), add(u,v+n,val+x), add(v+n,u,val+x), add(u+n, v+n, val), add(v+n, u+n, val);
        else if((c[u]=='L' && c[v]=='R')||(c[u]=='R'&&c[v]=='L'))
            add(u,v,val+x), add(v,u,val+x);
        else if(c[u]=='L' && c[v]=='M')
            add(u,v,val), add(v,u,val), add(u,v+n,val+x), add(v+n, u, val+x);
        else if(c[u]=='R' && c[v]=='M')
            add(u,v,val+x), add(v,u,val+x), add(u,v+n,val), add(v+n, u, val);
        else if(c[u]=='M' && c[v]=='L')
            add(u,v,val), add(v,u,val), add(u+n,v,val+x), add(v, u+n, val+x);
        else if(c[u]=='M' && c[v]=='R')
            add(u,v,val+x), add(v,u,val+x), add(u+n,v,val), add(v, u+n, val);
    }
    dijkstra();
    if(c[t]=='M')   cout<<dis[2*n+1];
    else            cout<<dis[t];
    cout<<endl;
}

int main()
{
    scanf("%d",&T);
    while(T--)  solve();
    return 0;
}

Go Running

题目大意:

视跑道为轴，有若干学生在上面跑步
学生的跑步起止时间和方向和起始位置均未知，速度为1 m / s
有n个监控，监控会给出 t 和 x，表示当时间为t 的时候，x位置上至少有一个学生
求当前跑道最少有多少学生

思路:

可以将学生视为点，每次监控到的学生可以有两种来源（x-t）或者（x+t），每个学生都可以用一条斜率为1或者-1的直线去覆盖，则问题可以转化为直线最少有多少条，可以用二分图将（x-t）和（x+t）分别放在两边，再用网络流求一下最小覆盖

AC Code:

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N=2e6 +10;
int a, b, x, t, l, r, n, sp, ep;
int cnt;
int head[N];
int dis[N];
struct node
{
    int e;
    int v;
    int nxt;
}edge[N<<1];
inline int read(){
   int ans=0;char r=getchar();
   while(r<'0'||r>'9')r=getchar();
   while(r>='0'&&r<='9'){ans=ans*10+r-'0';r=getchar();}
   return ans;
}
inline void addl(int u,int v,int w)
{
    edge[cnt].e=v;
    edge[cnt].v=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt++;
}

bool bfs()//bfs找深度
{
    memset(dis,-1,sizeof(dis));//注意！不要忘了这句
    dis[sp]=0;//起点深度为0，从源向汇bfs
    queue<int>q;
    q.push(sp);
    while(!q.empty())
    {
        int r=q.front();q.pop();
        for(int i=head[r];i!=-1;i=edge[i].nxt)
        {
            int j=edge[i].e;
            if(dis[j]==-1&&edge[i].v)//如果这个点还没有被bfs且这条边的流量不为0
            {
                dis[j]=dis[r]+1;
                q.push(j);
            }
        }
    }
    return dis[ep]!=-1;//若不可以到终点（起点）就返回false 
}
int dfs(int u,int flo)//dfs就是求节点u及其子树在残量为flo时的最大增量 
{
    if(u==ep)return flo;//如果是汇，直接返回flo
    int detla=flo;//用一个变量来保存flo，以方便更新其剩余残量
    for(int i=head[u];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].e;
        if(dis[v]==(dis[u]+1)&&(edge[i].v)>0)//如果满足深度条件且边可以走
        {
            int d=dfs(v,min(detla,edge[i].v));//向下递归
            //求v及其后续节点在残量为min(detla,edge[i].v)时的最大流量
            edge[i].v-=d;edge[i ^ 1].v+=d;//边的处理
            //注意，编号为i的边的反向边的编号为i^1,这是根据存边时的cnt决定的
            detla-=d;//将本节点的剩余残量值更新
            if(detla==0)break;//如果本节点已经没有残量可消耗了，就返回
        }
    }
    return flo-detla;//返回这个点已经被允许流过的流量
}
int dini()//求最大流量
{
    int ans=0, t;
    while(bfs())
    {
        while(t=dfs(sp, INF))   ans+=t;
    }
    return ans;
}


void solve()
{
    memset(head,-1,sizeof(head)); cnt=0;
    cin>>n;
    unordered_map<int,int>L;                //分别离散化二分图的两边
    unordered_map<int,int>R;
    int cntL=0, cntR=0;
    for(int i=1; i<=n; i++){
        cin>>t>>x;
        if(L.count(x+t))  l=L[x+t];
        else    L[x+t]=++cntL, l=cntL;

        if(R.count(x-t))    r=R[x-t];
        else    R[x-t]=++cntR, r=cntR;

        addl(l, r+n, 1);                    //加边
        addl(r+n, l, 0);    
    }
    sp=2*n+1, ep=2*n+2;                     //sp为源点，ep为汇点
    for(int i=1; i<=n; i++) addl(sp,i,1), addl(i,sp,0);
    for(int i=1+n; i<=2*n; i++) addl(i,ep,1), addl(ep,i,0);
    cout<<dini()<<endl;
}

int main()
{
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}