初识生成对抗网络GAN

(2014微软实习生笔试题)2.K-th string

$$\phi$$

$$\in$$

// 判断有向图中是否存在环，存在输出YES，不存在输出NO

#include

#define DEBUG
using namespace std;

const int maxn = 1e5 + 5;
int N, M;
vector edge[maxn];
int state[maxn]; // 0表示未访问，1表示未访问完子节点，2表示访问完子节点
bool flag;

void dfs(int node)
{
if (flag) return;
state[node] = 1;
for (int nextNode : edge[node]) {
if (1 == state[nextNode]) {
flag = true;
return;
}
if (2 != state[nextNode]) dfs(nextNode);
}
state[node] = 2;
return;
}

int main()
{

#ifdef DEBUG
    freopen("./data.in", "r", stdin);
    //freopen("./data.out","w",stdout);
#endif // DEBUG
int T; cin >> T;
while (T--) {
    for (int i = 0; i < maxn; i++) edge[i].clear();
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
    }
    memset(state, 0, sizeof(state));
    flag = false;
    for (int i = 1; i <= N; i++) {
        dfs(i);
        if (true == flag) break;
    }
    if (flag) cout << "YES" << endl;
    else cout << "NO" << endl;
}
return 0;

}

/*
2
5 5
1 2
2 3
4 5
5 4
4 2
3 2
1 2
2 3

YES
NO
*/

#include

#define DEBUG
using namespace std;

const int maxn = 1e5 + 5;

int main()
{

#ifdef DEBUG2
    freopen("./data.in", "r", stdin);
    //freopen("./data.out","w",stdout);
#endif // DEBUG
vector<int> v(5);
v[2] = 23;
cout << v[2] << endl;

v.clear();
cout << v[2] << endl;

// 忘记了，好像需要一个函数赋值的功能，记得总结
int n1 = 7, n2 = 7, n3 = 7;
n1 >>= 1;
n2 >= 1;
n3 = (n3 > 1);
cout << n1 << ' ' << n2 << ' ' << n3 << endl;
return 0;

}

// 判断有向连通图中的起点和终点

#include

#define DEBUG
using namespace std;

const int maxn = 1e5 + 5;

int main()
{

#ifdef DEBUG
    freopen("./data.in", "r", stdin);
    //freopen("./data.out","w",stdout);
#endif // DEBUG

int N; cin >> N;
map<string, int> inDegree, outDegree; // 出度和入度
string s, e;            // 答案起点和终点
set<string> all;        // 所有的城市

for (int i = 0; i < N; i++) {
    string s1, s2;
    cin >> s1 >> s2;
    outDegree[s1]++;
    inDegree[s2]++;
    all.insert(s1);
    all.insert(s2);
}
for (string city : all) {
    if (1 == inDegree[city] - outDegree[city]) e = city;
    if (1 == outDegree[city] - inDegree[city]) s = city;
}
cout << s << ' ' << e << endl;
return 0;

}

// 有M种物品，每种物品有数量A和价值P，S是每种物品最大值放在N的一个存储槽中

#include

#define DEBUG
using namespace std;

const int maxn = 1e4 + 5;

int main()
{

#ifdef DEBUG
    freopen("./data.in", "r", stdin);
    //freopen("./data.out","w",stdout);
#endif // DEBUG

int N, M;
int A[maxn], P[maxn], S[maxn];
cin >> N >> M;
for (int i = 0; i < M; i++) cin >> A[i];
for (int i = 0; i < M; i++) cin >> P[i];
for (int i = 0; i < M; i++) cin >> S[i];

long long value[maxn * 10], cnt = 0; // 注意这里的内存大小
for (int i = 0; i < M; i++) {
    int quo = A[i] / S[i];
    int rem = A[i] % S[i];
    for (int j = 0; j < quo; j++) {
        value[cnt++] = S[i] * P[i];
    }
    if (rem) value[cnt++] = rem * P[i];
}
sort(value, value + cnt);
long long ans = 0;
for (int i = cnt - 1; i >= cnt - N; i--) ans += value[i];
cout << ans << endl;
return 0;

}

// 计算所有两个数对之间的二进制位不同的总个数

#include

#define DEBUG
using namespace std;

const int maxn = 1e5 + 5;

int main()
{

#ifdef DEBUG
    freopen("./data.in", "r", stdin);
    //freopen("./data.out","w",stdout);
#endif // DEBUG

int N, arr[maxn];
cin >> N;
for (int i = 0; i < N; i++) cin >> arr[i];
long long ans = 0;
for (int i = 0; i < 32; i++) {
    int x = 0, y = 0;
    for (int j = 0; j < N; j++) {
        if (arr[j] & 1) x++;
        else y++;
        arr[j] >>= 1;
    }
    ans += x * y;
}
cout << ans << endl;
return 0;

}

#include
using namespace std;

const int maxn = 1e5 + 5;

int main()
{
int N, arr[maxn];
cin >> N;
for (int i = 0; i < N; i++) cin >> arr[i];

int l = *min_element(arr, arr + N), r = *max_element(arr, arr + N);
while (l < r) {
    int mid = (l + r) / 2;
    int small = 0, large = 0;
    for (int i = 0; i < N; i++) {
        if (arr[i] > mid) {
            large += (arr[i] - mid) / 2;
        }
        else if (arr[i] < mid) {
            small += mid - arr[i];
        }
    }
    if (small <= large) {

        break;
    }
    else {
        r = mid;
    }
}
return 0;

}

初识生成对抗网络GAN

赏个糖吃吧~