201403第1次

视频题解

第 1 题相反数¶

题目链接: 相反数

TAG: 桶 哈希

思路:

开两个数组作为两个桶分别记录正数和负数即可

代码:

#include<bits/stdc++.h>
using namespace std;

const int N=1010;

int a[N],b[N];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        if(t>0)a[t]++;
        else b[-t]++;
    }
    int ans=0;
    for(int i=1;i<=1000;i++){
        if(a[i]&&b[i]){
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

第 2 题窗口¶

题目链接: 窗口

TAG: 模拟

思路:

数组模拟屏幕和窗口即可，0代表没有窗口，i代表窗口序号为i

代码:

#include<bits/stdc++.h>
using namespace std;

const int N=3000;

struct Node{
    int id,x1,y1,x2,y2;
}node[11];

int w[N][N];

void change(int i){
    for(int j=node[i].x1;j<=node[i].x2;j++){
        for(int k=node[i].y1;k<=node[i].y2;k++){
            w[j][k]=node[i].id;
        }
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>node[i].x1>>node[i].y1>>node[i].x2>>node[i].y2;
        node[i].id=i;
        change(i);
    }
    while(m--){
        int x,y;
        cin>>x>>y;
        if(!w[x][y])cout<<"IGNORED\n";
        else{
            cout<<w[x][y]<<"\n";
            change(w[x][y]);
        }
    }
    return 0;
}

第 3 题命令行选项¶

题目链接: 命令行选项

TAG: STL 大模拟

思路:

读懂题意就容易了，使用stringstream能够大大减少代码量

代码:

#include<bits/stdc++.h>
using namespace std;

const int N=30;

bool a[N],b[N];
string ans[N];

int main(){
    string s;
    cin>>s;
    for(int i=0;s[i];i++){
        if(i+1<(int)s.size()&&s[i+1]==':'){
            b[s[i]-'a']=true;
            i++;
        }else{
            a[s[i]-'a']=true;
        }
    }
    int n;
    cin>>n;
    getchar();
    for(int i=1;i<=n;i++){
        cout<<"Case "<<i<<":";
        getline(cin,s);
        stringstream ss(s);
        vector<string> ops;
        while(ss>>s)ops.push_back(s);
        for(int i=0;i<26;i++)ans[i].clear();
        for(int i=1;i<(int)ops.size();i++){
            if(ops[i][0]!='-'||ops[i][1]<'a'||ops[i][1]>'z'||(int)ops[i].size()!=2)break;
            int k=ops[i][1]-'a';
            if(a[k])ans[k]="*";
            else if(b[k]&&i+1<(int)ops.size())ans[k]=ops[i+1],i++;
            else break;
        }
        for(int i=0;i<26;i++){
            if(ans[i].size()){
                cout<<" -"<<(char)(i+'a');
                if(b[i])cout<<" "<<ans[i];
            }
        }
        cout<<"\n";
    }
    return 0;
}

第 4 题无线网络¶

题目链接: 无线网络

TAG: 单源最短路 BFS

思路:

将前n个固定点,m个待选择点存入节点数组p,之后计算数组中每两个点间的距离，如果距离小于r，就在这两点之间建立一条无向边；关系建立后进行bfs；dist[i][j]表示第i个点的路径中增设路由器的数量为j的最短距离；由于题目询问的是路径上路由器的最少数量，实际不用考虑计算路径长度，只需要把点的数量当做所谓的长度进行计算。

代码:

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
typedef long long ll;
const int N=210,M=40100;

int n,m,k,r;
int h[N],e[M],ne[M],idx;
PII p[N];
int dist[N][N];

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool check(PII a,PII b){
    ll x=a.first-b.first;
    ll y=a.second-b.second;
    return x*x+y*y<=(ll)r*r;
}

int bfs(){
    queue<PII> q;
    q.push({1,0});
    memset(dist,0x3f,sizeof dist);
    dist[1][0]=0;
    while(!q.empty()){
        PII t=q.front();
        q.pop();
        for(int i=h[t.first];~i;i=ne[i]){
            int x=e[i];
            int y=t.second;
            if(x>n)y++;
            if(y<=k){
                if(dist[x][y]>dist[t.first][t.second]+1){
                    dist[x][y]=dist[t.first][t.second]+1;
                    q.push({x,y});
                }
            }
        }
    }
    int res=1e8;
    for(int i=0;i<=k;i++){
        res=min(res,dist[2][i]);
    }
    return res-1;
}

int main(){
    cin>>n>>m>>k>>r;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n+m;i++)cin>>p[i].first>>p[i].second;
    for(int i=1;i<=n+m;i++){
        for(int j=i+1;j<=n+m;j++){
            if(check(p[i],p[j])){
                add(i,j);
                add(j,i);
            }
        }
    }
    cout<<bfs();
    return 0;
}

第 5 题任务调度¶

题目链接: 任务调度

TAG: DP

思路:

先为每个任务在4种资源配置中选择一种；再安排所有任务的执行顺序即可

经过分析可得：一个程序至少会占用一个CPU，一共只有两个CPU，所以同时最多有两个程序运行。且如果同时有两个程序运行，那么每个程序都会占用一个CPU

可以将两个CPU分离，认为其中一个CPU附带GPU，不会对答案造成影响

接下来考虑任务顺序。可以发现，对于占用全部资源的任务，可以调度其在最开始就运行。这样，在开始的一段时间，资源是满载的，不需要等待资源释放就可以运行。

而对于其它任务，由于任务之间没有依赖关系，而又分别只占用一个CPU+GPU或一个CPU，令其依次执行即可。

代码:

#include<bits/stdc++.h>
using namespace std;

const int N=1010;

int main(){
    int n,a,b,c,d;
    cin>>n;
    int f[N][N*10];
    memset(f,0x3f,sizeof f);
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        cin>>a>>b>>c>>d;
        c=min(a,c);
        b=min(min(b,d),c);
        for(int j=0;j<=i*10;j++){
            f[i][j]=f[i-1][j]+a;
            if(j>=c)f[i][j]=min(f[i][j],f[i-1][j-c]);
            if(j>=b)f[i][j]=min(f[i][j],f[i-1][j-b]+b);
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<=n*10;i++){
        ans=min(ans,max(i,f[n][i]));
    }
    cout<<ans;
    return 0;
}

201403第1次

第 1 题 相反数¶

第 2 题 窗口¶

第 3 题 命令行选项¶

第 4 题 无线网络¶

第 5 题 任务调度¶

评论