模拟赛

成功爆0

提交时没有想到默认不是C++

痛失115

T1

将一个字符串的in换成out或ans就能匹配

问匹配个数

出题人良心送分

$n^2*l$暴力即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
string a[maxn];
int n;
int ans;
bool check(string x,string y)
{
    bool flag=0;
    if(x.size()>y.size())
    swap(x,y);
    if(y.size()!=x.size()+1)
    {
        return 0;
    }
    for(int i=0,j=0;i<x.size(),j<y.size();)
    {
        if(x[i]!=y[j] && flag==1) return 0;
        if(x[i]!=y[j] && flag==0)
        {
            if(i==x.size()-1) return 0;
            if(x[i]=='i' && x[i+1]=='n' && (y[j]=='a'  && y[j+1]=='n' && y[j+2]=='s') ||(y[j]=='o' && y[j+1]=='u' && y[j+2]=='t'))
            {
                flag=1;
                i+=2;
                j+=3;
            }
            else return 0;
        }
        else i++,j++;
    }
    if(flag==1) return 1;
    return 0;
}
int main()
{
    freopen("judge.in","r",stdin);
    freopen("judge.out","w",stdout);
    cin>>n;
    getline(cin,a[0]);
    for(int i=1;i<=n;i++)
    {
        getline(cin,a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<a[i].size();j++)
        {
            if(a[i][j]>='A' && a[i][j]<='Z')
            {
                a[i][j]=char(a[i][j]+32);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            ans+=check(a[i],a[j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

T2

动态规划

用到一个技巧：当某一维的状态较大时 将状态与目标函数交换

因为p较大 e较小

将定义的$f[i][h][p][g]=e$换成 $f[i][h][e][q]=p$

#include<bits/stdc++.h>
using namespace std;
int f[45][15][405][405];
int ans;
int n,m,H,c;
struct node
{
    int h,p,g,e;
}a[15];
signed main()
{
    freopen("grid.in","r",stdin);
    freopen("grid.out","w",stdout);
    // freopen("1.in","r",stdin);
    cin>>n>>m>>H>>c;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].h>>a[i].p>>a[i].g>>a[i].e;
    }
    memset(f,0xc0,sizeof f);
    f[0][H][0][0]=0;
    for(int i=0;i<=m;i++)
    {
        for(int h=0;h<=H;h++)
        {
            for(int g=0;g<=400;g++)
            {
                for(int e=0;e<=400;e++)
                {
                    if(f[i][h][g][e]<0) continue;
                    ans=max(ans,e);
                    if(i>=m) continue;
                    for(int j=1;j<=n;j++)
                        if (h + a[j].h >= 0 && g + a[j].g >= 0 && e + a[j].e >= 0)
                            f[i + 1][h + a[j].h][g + a[j].g][e + a[j].e]=max(f[i + 1][h + a[j].h][g + a[j].g][e + a[j].e],f[i][h][g][e] + a[j].p);
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

讲评时提到记忆化搜索+剪枝可以用广搜实现

T3

数论+线段树

题面与裴蜀定理一模一样

所以个数为s除以区间gcd

单点修改+区间gcd

用线段树维护

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+10; 
int gcd(int a,int b)
{
    if(a%b==0) return b;
    return gcd(b,a%b);
}
int gcdd[maxn*4];
int a[maxn*4];
void push_up(int id)
{
    gcdd[id]=gcd(gcdd[id*2],gcdd[id*2+1]);
}
void change(int id,int l,int r,int x,int k)
{
    if(l==r) 
    {
        gcdd[id]=k;
        return ;
    }
    int mid=l+r>>1;
    if(x<=mid) change(id*2,l,mid,x,k);
    else change(id*2+1,mid+1,r,x,k);
    push_up(id);
}
void build(int id,int l,int r)
{
    if(l==r) 
    {
        gcdd[id]=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    push_up(id);
}
int query(int id,int l,int r,int x,int y)
{
    if(x<=l && y>=r)
    {
        return gcdd[id];
    }
    int mid=l+r>>1;
    if(x<=mid && y>mid) return gcd(query(id*2,l,mid,x,y),query(id*2+1,mid+1,r,x,y));
    if(x<=mid) return query(id*2,l,mid,x,y);
    return query(id*2+1,mid+1,r,x,y);
}
int T,c;
int n,m;
signed main()
{
    freopen("equation.in","r",stdin);
    freopen("equation.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>T>>c;
    while(T--)
    {
        memset(gcdd,0,sizeof gcdd);
        memset(a,0,sizeof a);
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            int opt;
            cin>>opt;
            if(opt==1)
            {  
                int x,k;
                cin>>x>>k;
                change(1,1,n,x,k);
            }
            else
            {
                int l,r,s;
                cin>>l>>r>>s;
                cout<<s/query(1,1,n,l,r)<<'\n';
            }
        }
    }
    return 0;
}

question：

区间gcd的时间复杂度

T4

其实做过两道分层图最短路之后

感觉自己有可能想出来拆点的方法

但是比赛时 没太去想

图论建模+最短路

将地铁线路经过的车站新建点 向车站的点连-val的边 表示下车

车站向下一个点的新建点连dis的边 表示上车

新建点向下一个新建点连dis的边 表示继续走

因为边权有负的 又是多源最短路

用到了johnson 算法

定义一个新点 向所有点连边权为0的边

跑SPFA 求出各点的势h[]（像是电势 重力势等）

然后改边权 $w=w+h[u]-h[v]$

这样保证了边权非负

再跑n边dij即可

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn=4005;
struct edge
{
    int nxt;
    int v;
    int w;
}e[maxn*1000];
int head[maxn*100];
int cnt;
struct node
{
    int x;
    int y;
    int val;
}p[maxn*10];
int dis[maxn][maxn];
int h[maxn];
bool vis[maxn];
int nn,mm;
int t[maxn];
int pointcnt;
bool SPFA(int n) 
{
    memset(h,0x3f3f,sizeof h);
    memset(vis,0, sizeof(vis));
    h[n + 1] = 0;
    queue<int> Q;
    Q.push(n + 1);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        vis[u] = 0;
        for (int i =head[u];i;i=e[i].nxt) {
            int v = e[i].v;
            int w = e[i].w;
            if (h[v] > h[u] + w) {
                h[v] = h[u] + w;
                if (!vis[v]) {
                    vis[v] = 1;
                    Q.push(v);
                    t[v]++;
                    if (t[v] == n + 1) return false;
                }
            }
        }
    }
    return 1;
}
void Dijkstra(int SS) {
    memset(vis,0,sizeof vis);
    memset(dis[SS], 0x3f3f, sizeof(dis[SS]));
    dis[SS][SS] = 0;

    priority_queue<pair<int,int> > Q;
    Q.push(make_pair(0, SS));

    while (!Q.empty()) {
        int u=Q.top().second;
        Q.pop();
        if(vis[u]) continue;
        vis[u]=1;
       for(int i=head[u];i;i=e[i].nxt)
       {
            int v=e[i].v;
            int w=e[i].w;
            if(dis[SS][v]>dis[SS][u]+w)
            {
                dis[SS][v]=dis[SS][u]+w;
                Q.push(make_pair(dis[SS][v],v));
            }

       }
    }
}
void Johnson(int n) {
    SPFA(n); 
    for (int u = 1; u <= n; u++) 
       for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            e[i].w=e[i].w+h[u]-h[v];
            cout<<e[i].w<<endl;
        }
    for (int i = 1; i <= nn; i++)
        Dijkstra(i);
}
void addedge(int u,int v,int w)
{
    e[++cnt].nxt=head[u];
    e[cnt].v=v;
    e[cnt].w=w;
    head[u]=cnt;
}
int diss(node a,node b)
{
    return ceil(sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
signed main() 
{
    freopen("1.in","r",stdin);
    cin>>nn>>mm;
    for(int i=1;i<=nn;i++)
    {
        cin>>p[i].x>>p[i].y>>p[i].val;
    }
    pointcnt=nn;
    for(int i=1;i<=mm;i++)
    {
        int pp;
        int now;
        int last;
        cin>>pp;
        cin>>now;
        pointcnt++;
        addedge(pointcnt,now,-p[now].val);
        for(int j=2;j<=pp;j++)
        {
            cin>>last;
            pointcnt++;
            int dis=diss(p[now],p[last]);
            addedge(now,pointcnt,dis);
            addedge(pointcnt-1,pointcnt,dis);
            now=last;
            addedge(pointcnt,now,-p[now].val);
        }
    }
    for(int i=1;i<=pointcnt;i++)
    addedge(pointcnt+1,i,0);
    Johnson(pointcnt);
    for(int i=1;i<=nn;i++)
    {
        for(int j=1;j<=nn;j++)
        {
            cout<<-(dis[i][j]+h[j]-h[i])+p[i].val<<' ';
        }
        cout<<endl;
    }
    return 0;
}

不知道为什么调不出来 还有问题

细节挺多

比如负权+多源最短路 用Johnson

比如调整边权的正负 将题目所求转化成最短路

预习

准备明天学习DP和图论