网易互娱服务端4a题解(cpp)
阿已经连续微众拼多多网易互娱快乐ak了 希望周一能拿到美团oc结束0offer悲剧
t4 简单分析可知是一个有向无环图 可以通过构建一个连接全部节点的虚节点进行队列优化的BFS
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
#define maxn 100
using namespace std;
vector<int>G[maxn];
void addedge(int l,int r){
G[l].push_back(r);
}
int boxes[100][3];
int main(){
int boxesRowLen;
cin >> boxesRowLen;
for(int i = 0; i < boxesRowLen; i++){
cin >> boxes[i][0] >> boxes[i][1] >> boxes[i][2];
addedge(0,i+1);
}
for(int i = 0; i < boxesRowLen; i++){
for(int j = 0; j < boxesRowLen; j++){
if(boxes[i][0] < boxes[j][0] && boxes[i][1] < boxes[j][1] && boxes[i][2] < boxes[j][2]) {
addedge(i+1,j+1);
}
}
}
queue<int>que;
bool inq[maxn];
memset(inq,0,sizeof(inq));
int dist[maxn];
memset(dist, -1, sizeof(dist));
dist[0] = 0;
que.push(0);
int ans = 0;
while(!que.empty()) {
int k = que.front();
inq[k] = 0;
que.pop();
for(int i = 0; i < G[k].size(); i++){
int v = G[k][i];
if(dist[v] == -1 || dist[v] < dist[k] + 1){
dist[v] = dist[k]+1;
ans = max(ans,dist[v]);
if(!inq[v]){
inq[v] = 1;
que.push(v);
}
}
}
}
cout << ans;
}t3 恶心lenDFS 就正常暴搜 我在最后10min才发现新选择的节点还要对其依赖进行放置，并确保没和不喜欢的放在一起，改了7min差3min就***叹人生的时候莫名其妙过了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#define maxn 9
#define maxm 9
#define maxx 52
using namespace std;
bool hate[maxx][maxx];
bool lov[maxx][maxx];
char nam[maxx];
int pick[maxm][maxn];
bool vis[maxx];
int n,m;
inline int toid (int i, int j){
return i*m + j;
}
bool flg = 0;
void DFS(int tm,int tn){
if(flg)
return;
if(tn == n){
flg = 1;
//cout << "adsdasdasdas";
return;
}
if(pick[tm][tn] == -1){
for(int i = 0; i < m; i++){
int t = toid(tn,i);
if(!vis[t]) {
bool flgg = 1;
for(int j = 0; j < tn; j++){
int c = pick[tm][j];
if(hate[c][t]){
flgg = 0;
break;
}
}
queue<int>que;
que.push(t);
queue<int>quee;
while(!que.empty()){
int k = que.front();
que.pop();
for(int j = 0; j < n; j++){
if(pick[tm][j] == -1)
continue;
int c = pick[tm][j];
if(hate[c][k]){
flgg = 0;
break;
}
}
for(int j = 0; j < maxx; j++){
if (j == t)
continue;
if(lov[t][j]){
if(!vis[j] && pick[tm][j/m] == -1){
que.push(j);
quee.push(j);
pick[tm][j/m] = j;
} else if(pick[tm][j/m] == j){
continue;
}else{
flgg = 0;
}
}
}
}
if(flgg){
vis[t] = 1;
pick[tm][tn] = t;
if(tm == m-1)
DFS(0,tn+1);
else
DFS(tm+1,tn);
if(flg)
return;
vis[t] = 0;
pick[tm][tn] = -1;
}
while(!quee.empty()){
int k = quee.front();
quee.pop();
pick[tm][k/m] = -1;
vis[k] = 0;
}
}
}
}else{
if(tm == m-1)
DFS(0,tn+1);
else
DFS(tm+1,tn);
}
return;
}
int main(){
cin >> n >> m;
memset(pick,-1,sizeof(pick));
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j++) {
int c = toid(i,j);
cin >> nam[c];
}
}
int ai,aj,bi,bj;
char c;
while(cin >> ai >> aj >> c >> bi >> bj) {
if(ai == 0)
break;
if(c == 'N'){
int ta = toid(ai-1,aj-1), tb = toid(bi-1,bj-1);
//cout << "hate" << nam[ta] << " " << nam[tb] << endl;
hate[ta][tb] = 1;
hate[tb][ta] = 1;
}
if(c == 'Y'){
int ta = toid(ai-1,aj-1), tb = toid(bi-1,bj-1);
//cout << "love" << nam[ta] << " " << nam[tb] << endl;
lov[ta][tb] = 1;
lov[tb][ta] = 1;
}
}
queue<int>que;
for(int i = 0; i < m; i++){
que.push(i);
vis[i] = 1;
pick[i][0] = i;
while(!que.empty()){
int k = que.front();
que.pop();
for(int j = 0; j < m*n; j++){
if(lov[k][j] && !vis[j]){
pick[i][j/m] = j;
vis[j] = 1;
que.push(j);
}
}
}
}
/*for(int i = 0; i < m; i++){
for(int j = 0; j < n; j ++) {
cout<<pick[i][j] << " ";
}
cout <<endl;
}*/
DFS(0,1);
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++) {
cout<< nam[pick[i][j]];
}
cout <<endl;
}
}t2 把两个数组从小到大排序一下，对员工技能熟练度从小到大遍历 同时使用一个指针来找到可以被当前员工完成的全部任务的个数k，然后就1(k1-i1+1)(k2-i2+1)..... 就出来了
一开始完全没思路 后来看着看着数据觉得 333 321 = 6有点奥妙重重 然后就想出来了
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 100000
using namespace std;
int t[maxn],c[maxn];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> t[i];
}
for(int i = 0; i < n; i++){
cin >> c[i];
}
long long m;
cin >> m;
int j = 0;
long long ans = 1;
sort(t,t+n);
sort(c,c+n);
for(int i = 0; i < n; i++){
while(j < n && c[j] <= t[i])
j++;
if(c[j] > t[i] || j == n)
j--;
//cout << j+1-i<<endl;
ans*=(j+1-i);
ans%=m;
}
cout << ans;
}t1 简单字符串操作 写的时候因为今天一天就睡了4个小时 出现了无数的bug 希望能赶紧被给个offer 焦虑的天天睡不着可太难受了
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
string num1,num2;
cin >> num1 >> num2;
//num1 = "";
//num2 = "";
int num1pos = num1.size();
for(int i = 0; i < num1.size(); i++){
if(num1[i] == '.') {
num1pos = i;
break;
}
}
int num2pos = num2.size();
for(int i = 0; i < num2.size(); i++){
if(num2[i] == '.') {
num2pos = i;
break;
}
}
string num1r = "";
if(num1pos != num1.size())
num1r = num1.substr(num1pos+1,num1.size() - num1pos);
string num2r = "";
if(num2pos != num2.size())
num2r = num2.substr(num2pos+1,num2.size() - num2pos);
string num1l = num1.substr(0,num1pos);
string num2l = num2.substr(0,num2pos);
//cout << num1l << endl << num1r << endl << num2l << endl << num2r<<endl;
if(num1r.size() < num2r.size()){
string k = num2r;
num2r = num1r;
num1r = k;
}
//cout << num1r << endl;
int jin = 0;
for(int i = num1r.size() - 1; i >= 0; i--){
if( i < num2r.size() ){
int k = num2r[i] + num1r[i] + jin;
k -= 96;
jin = k/9;
k = k%9;
num1r[i] = k+'0';
}
}
if(num1l.size() < num2l.size()){
string k = num1l;
num1l = num2l;
num2l = k;
}
for(int i = 0; i < num1l.size(); i++){
if(i < num2l.size() || jin != 0){
int k = num1l[num1l.size() - i -1] - 48 + jin;
if(i < num2l.size())
k += num2l[num2l.size() - i -1] - 48;
jin = k/9;
k = k%9;
num1l[num1l.size() - i -1] = k+'0';
}
}
string c = "";
if(jin != 0)
c += "1";
c+=num1l;
if(num1r.size()){
c+=".";
c+=num1r;
}
cout << c;
}#网易笔试#
投递科锐国际等公司8个岗位