首页 > 9.13 网易雷火 3.82/4
头像
牛客691621789号
编辑于 2020-09-14 11:47
+ 关注

9.13 网易雷火 3.82/4

第一题
#include<iostream>
#include<vector>
using namespace std;


int main()
{
    int x, y, z, N, M;
    double xlen, ylen, zlen;
    cin >> x >> y >> z >> xlen >> ylen >> zlen;
    cin >> N >> M;
    xlen = xlen / 2;
    ylen = ylen / 2;
    zlen = zlen / 2;
    int xN, yN, zN;
    double xlenN, ylenN, zlenN;
    int xM, yM, zM, rM;
    int ans = 0;
    for(int i = 1; i <= N; ++i)
    {
        cin >> xN >> yN >> zN >> xlenN >> ylenN >> zlenN;
        xlenN = xlenN / 2;
        ylenN = ylenN / 2;
        zlenN = zlenN / 2;
        if((x + xlen > xN + xlenN) && 
           (x - xlen < xN - xlenN) && 
           (y + ylen > yN + ylenN) && 
           (y - ylen < yN - ylenN) && 
           (z + zlen > zN + zlenN) && 
           (z - zlen < zN - zlenN)
          )
            ++ans;
    }
    for(int i = 1; i <= M; ++i)
    {
        cin >> xM >> yM >> zM >> rM;
        if((x + xlen > xM + rM) && 
           (x - xlen < xM - rM) && 
           (y + ylen > yM + rM) && 
           (y - ylen < yM - rM) && 
           (z + zlen > zM + rM) && 
           (z - zlen < zM - rM)
          )
            ++ans;
    }
    
    cout << ans << endl;
}

第二题
#include<iostream>
#include<vector>
#include<string.h>
#include<stdio.h>
using namespace std;

double V[105];
double P[105][105];
double T[105][105];
int main()
{
    int N, X, t;
    cin >> N >> X >> t;
    for(int i = 1; i <= N; ++i) cin >> V[i];
    for(int i = 1; i < N; ++i)
    {
        for(int j = i + 1; j <= N; ++j)
        {
            cin >> P[i][j];
        }
    }
    for(int i = 1; i < N; ++i)
    {
        for(int j = i + 1; j <= N; ++j)
        {
            cin >> T[i][j];
        }
    }
    int maxn = 0xffff;
    vector<double> dp(105, maxn);
    dp[X] = 0;
    for(int i = 1; i <= N; ++i)
    {
        if(i == X) continue;
        dp[i] = V[i] / t;
        for(int j = 1; j < i; ++j)
        {
            dp[i] = min(dp[i], dp[j] + T[j][i] + P[j][i] / t);
        }
    }
    printf("%.2f\n", dp[N]);
    
}
第三题

这题只过了82左右,不知道什么没考虑到,因为dis(A,B) = min(dis(A,C) + dis(C,B)),所以其实就是很多个相邻的三角形连接起来的路径,然后用dp去更新,调整坐标,总是从左下角走到右上角,不过貌似还是有些问题。
#include<vector>
#include<iostream>
#include<map>
#include<math.h>
using namespace std;

double root3 = sqrt(1 - 0.5*0.5);
// root3 / 1 = 0.5 / l
double l = 0.5 / root3;
double s = root3 - l;

// 1 为倒 2 为正
int judge(int x, int y)
{
    if((x & 1)){
        if(y & 1) return 2;
        else return 1;
    }
    else{
        if(y & 1) return 1;
        else return 2;
    }
}
double ss = s * 2;
double ll = l * 2;

int main()
{
    int x11, x22, y11, y22;
    cin >> y11 >> x11 >> y22 >> x22;
    int x1 = 2, y1 = 2;
    int x2 = abs(x11 - x22) + 2, y2 = abs(y11 - y22) + 2;
    if(judge(x11, y11) == 2){
        x1 = 3;
        x2 += 1;
    }
    vector<vector<double> > dp(1005, vector<double>(1005, 10000));
    dp[x1][y1] = 0;
    for(int i = x1; i <= x2; ++i)
    {
        int tmp = i - x1;
        dp[i][y1] = (tmp >> 1);
        if(tmp & 1) dp[i][y1] += ss;
    }
    int cnt1 = 0, cnt2 = 0;
    for(int i = y1; i <= y2; ++i)
    {
        dp[x1][i] = cnt1 * ss + cnt2 * ll;
        if(i&1) ++cnt1;
        else ++cnt2;
    }
    for(int i = x1 + 1; i <= x2; ++i)
    {
        for(int j = y1 + 1; j <= y2; ++j)
        {
            if(judge(i, j) == 2)
            {
                dp[i][j] = min(dp[i - 1][j] + ss, dp[i - 2][j] + 1);
                dp[i][j] = min(dp[i][j], dp[i - 2][j - 1] + ll);
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + ss);
            }
            else{
                dp[i][j] = min(dp[i - 2][j] + 1, dp[i - 1][j] + ss);
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + ll);
            }
        }
    }
    printf("%.4f\n", dp[x2][y2]);
}

第四题
模拟题,就是恶心
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
using namespace std;

    int N, M, X, Y, count;
    map<string,bool> red;
    //map<string,set<string> > redset;
    //map<string,set<string> > button;
    //map<string,set<string> > panel;

    map<string,int > redsetc;
    map<string,int > buttonc;
    map<string,int > panelc;
    // rev
    map<string,set<string> > revset;
    map<string,set<string> > revbutton;
    map<string,set<string> > revpanel;
vector<string> order;
set<string> ans;

void updateSet(const string& name, bool open);
void updateButton(const string& name, bool open);
void updatePanel(const string& name1, bool open);

void updateRed(const string& name, bool open)
{
    if(open == red[name]) return;
    updateSet(name, open);
    redsetc[name] = open;
    for(auto &name1 : revset[name])
    {
        if(!open){
            if(--redsetc[name1] == 0){
                updateSet(name1, false);
            }
        }
        else{
            if(redsetc[name1]++ == 0){
                updateSet(name1, true);
            }
        }
    }
}

void updateSet(const string& name, bool open)
{
    //cout << "updateSet " << name << endl;
    for(auto &name1 : revbutton[name])
    {
        if(!open){
            if(--buttonc[name1] == 0){
                updateButton(name1, false);
            }
        }
        else{
            if(buttonc[name1]++ == 0){
                updateButton(name1, true);
            }
        }
    }
}

void updateButton(const string& name, bool open)
{
    //cout << "updateButton " << name << endl;
    for(auto &name1 : revpanel[name])
    {
        if(!open){
            if(--panelc[name1] == 0){
                updatePanel(name1, false);
            }
        }
        else{
            if(panelc[name1]++ == 0){
                updatePanel(name1, true);
            }
        }
    }
}

void updatePanel(const string& name, bool open)
{
    //cout << "updatePanel " << name << endl;
    if(!open) ans.insert(name);
}

void show()
{
    for(auto &s : order){
        if(ans.count(s)) cout << s << endl;
    }
}
int main()
{
    
    cin >> N >> M >> X >> Y;
    string tmp, tmp2;
    bool state;
    for(int i = 0; i < N; ++i){
        cin >> tmp >> state;
        red[tmp] = state;
        revset[tmp] = {};
        // 伪造集合
        revbutton[tmp] = {};
        redsetc[tmp] = state;
        //redset[tmp] = {tmp};
    }
    for(int i = 0; i < M; ++i){
        //set<string> sset;
        cin >> tmp >> count;
        revbutton[tmp] = {};
        redsetc[tmp] = 0;
        for(int i = 0; i < count; ++i){
            cin >> tmp2;
            //sset.insert(tmp2);
            revset[tmp2].insert(tmp);
            if(red[tmp2]) ++redsetc[tmp];
        }
        //redset[tmp] = sset;
    }
    for(int i = 0; i < X; ++i)
    {
        //set<string> sset;
        cin >> tmp >> count;
        revpanel[tmp] = {};
        buttonc[tmp] = 0;
        for(int i = 0; i < count; ++i){
            cin >> tmp2;
            //sset.insert(tmp2);
            revbutton[tmp2].insert(tmp);
            if(redsetc[tmp2]) ++buttonc[tmp];
        }
        //button[tmp] = sset;
    }
    for(int i = 0; i < Y; ++i)
    {
        //set<string> sset;
        cin >> tmp >> count;
        order.push_back(tmp);
        panelc[tmp] = 0;
        for(int i = 0; i < count; ++i){
            cin >> tmp2;
            //sset.insert(tmp2);
            revpanel[tmp2].insert(tmp);
            if(buttonc[tmp2]) ++panelc[tmp];
        }
        //panel[tmp] = sset;
    }
    int S;
    string op, name1, name2;
    cin >> S;
    while(S--)
    {
        ans.clear();
        cin >> op;
        if(op == "Show")
        {
            cin >> name1;
            updateRed(name1, true);
            red[name1] = true;
        }
        else if(op == "Hide")
        {
            cin >> name1;
            updateRed(name1, false);
            red[name1] = false;
        }
        else if(op == "Ask")
        {
            cin >> name1;
            if(buttonc.find(name1) != buttonc.end()){
                if(!buttonc[name1]) cout << "NO" << endl;
                else cout << "YES" << endl;
            }
            else{
                if(!panelc[name1]) cout << "NO" << endl;
                else cout << "YES" << endl;
            }
        }
        else if(op == "Remove")
        {
            cin >> name1 >> name2;
            if(revbutton[name2].count(name1)){
                revbutton[name2].erase(name1);
                if(redsetc[name2]){
                    if(--buttonc[name1] == 0) updateButton(name1, false);
                }
            }
        }
        else if(op == "Bind")
        {
            cin >> name1 >> name2;
            if(!revbutton[name2].count(name1)){
                revbutton[name2].insert(name1);
                if(redsetc[name2]){
                    if(buttonc[name1]++ == 0) updateButton(name1, true);
                }
            }
        }
        show();
    }
}

全部评论

(8) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐