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();
}
}
