染色时间

题意

思路

优先队列广搜

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <map>
#include <vector>
#include <time.h>
#include <queue>

using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const int N=100000,MOD=1e9+7,INF=0x3f3f3f3f;

int mp[510][510];
int f[510][510];
bool st[510][510];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int n,m;
int ans=0;

priority_queue<pair<int,PII>> qu;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
            f[i][j]=INF;
        }
    }
//    clock_t startTime,endTime;
//    startTime = clock();

    qu.push({-mp[1][1],{1,1}});
    f[1][1]=mp[1][1];
    st[1][1]=true;
    while(!qu.empty()){
        auto tp=qu.top();
        qu.pop();
        int tt=-tp.first,x=tp.second.first,y=tp.second.second;
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx>n||ny>m||nx<1||ny<1||st[nx][ny]) continue;
            f[nx][ny]=tt+mp[nx][ny];
            st[nx][ny]=true;
            qu.push({-f[nx][ny],{nx,ny}});
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans=max(ans,f[i][j]);
        }
    }
    cout<<ans<<endl;
//    endTime = clock();//计时结束
//    cout << "The run time is: " <<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;

    return 0;
}

总结

先用bfs 会TLE，下面介绍计算程序运行时间的方法

clock_t startTime,endTime;
startTime = clock();


endTime = clock();//计时结束
cout << "The run time is: " <<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;

k 倍区间

题意

思路

满足条件的两个数s[i]、s[j]，当且仅当s[i]%k==s[j]%k && s[i]>=s[j]

计算前缀和%k后的结果，用map离散化。

对每个%k后的值，开一个数组，按顺序存储前缀和的原始值，这个数组的逆序对就是对答案的贡献。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <map>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;

int n,k;
LL a[100010];
LL s[100010];
map<LL,LL> mp;
LL ans,cnt,check;
vector<LL> li[100010];

void merg(vector<LL> &list,int l,int r){
    if(l>=r) return ;
    int mid=(l+r)>>1;
    merg(list,l,mid);
    merg(list,mid+1,r);
    int i=l,j=mid+1,kk=0;
    LL temp[r-l+1];

    while(i<=mid&&j<=r){
        if(list[i]>list[j])
            temp[kk++]=list[i++];
        else{
            temp[kk++]=list[j++];
            check+=mid-i+1;
        }
    }
    while(j<=r) temp[kk++]=list[j++];
    while(i<=mid){
        temp[kk++]=list[i++];
    }

    for(int ii=l,jj=0;ii<=r;ii++,jj++){
        list[ii]=temp[jj];
    }
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i],cout<<s[i]<<" ";
    cout<<endl;
    for(int i=0;i<=n;i++){
        LL temp = (s[i]%k+k)%k;
        if(mp[temp]!=0){
            li[mp[temp]].push_back(s[i]);
        }else{
            mp[temp]=++cnt;
            li[cnt].push_back(s[i]);
        }
    }
    for(int i=1;i<=cnt;i++){
//        for(auto x:li[i]) cout<<x<<" ";
//        cout<<endl;
        check=0;
        merg(li[i],0,li[i].size()-1);
        ans+=check;
    }
    cout<<ans<<endl;
    return 0;
}