day8 考试

ccj123

2025-02-05 20:26:04

发布于：上海

26阅读

0回复

0点赞

十二生肖

#include<bits/stdc++.h>
using namespace std;
long long n;
bool flag;
int main()
{
    cin>>n;
    string s = to_string(n);
	for(int i = 0;i < s.length()-1;i++)
	{
		if(s[i] == '1' && s[i+1] == '2') flag = true;
	}
	if(n % 12 == 0 || flag  ) cout << "YE5";
	else cout << "N0";
 }

草药丛？陷阱！ N^2

#include <iostream>
#include <iomanip> 
#include <cmath>  
using namespace std;
const int N = 1010;
int main() {
    int n;
    cin >> n;
    int a[n+1];
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        double sum = 0;
        int cnt[N] = {0};
        for (int j = i; j <= n; ++j) {
            sum += a[j];
            cnt[a[j]]++;
            double avg = sum / (j - i + 1);
            if (avg == (int)avg && cnt[(int)avg] > 0) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

N^3

#include<bits/stdc++.h>
using namespace std;
int n,m,x[111],y,num;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i];//输入草药 
    for(int L=1;L<=n;L++){
        y=0;
      	for(int R=L;R<=n;R++){
        	y+=x[R];
        	for(int u=L;u<=R;u++){
            	if(y==x[u]*(R-L+1)){
                	num++;
               		break;
            	}
            }
        }
    }
    cout<<num;
    return 0;
}

拓扑排序（填空）

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;;
std::vector<int> g[N];// 领接表存储图
int in[N];// 表示每个点的入度
queue<int> q;
void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        in[v]++;
    }
    // 遍历每个点，如果入度为 0 则加入队列
    for (int i=1;i<=n;i++){
        if (in[i]==0){
            q.push(i);
        }
    }
    //用 ans 来维护拓扑序
    vector<int> ans;
    // 当队列非空则继续执行
    while (!q.empty()) {
        // 拿出队首
        int u=q.front();
        // 弹出队首
        q.pop();
        // 把当前点加入拓扑序中
        ans.push_back(u);
        // 遍历所有相邻的点
        for(int v:g[u]){
            //相邻点的入度减一
            in[v]--;
            //如果相邻点入度为 0 ，则加入队列
            if(in[v]==0){
                q.push(v);
            }
        }
    }
    // 如果 ans.size() = n 说明无环，有拓扑序
    if(ans.size() == n){
        cout<<"YES"<<endl;
        for (int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
    }
    //不然说明有环
    else{
        cout<<"NO";
    }
}

int main()
{
    solve();
}

安全节点

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> out[400010];
int in[400010];
vector<int> ans;
queue<int> q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		in[u]++;
		out[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		if(!in[i]){
			q.push(i);
			ans.push_back(i);
		}
	}
	while(!q.empty()){
		int t=q.front();
		q.pop();
		for(int x:out[t]){
			in[x]--;
			if(!in[x]){
				q.push(x);
				ans.push_back(x);
			}
		}
	}
	cout<<ans.size()<<endl;
	sort(ans.begin(),ans.end());
	for(int x:ans) cout<<x<<" ";
    return 0;
}

无垠的树

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

vector<int> g[400010];
int vis[400020],in[400020];
queue<int> q;
int T,n,u,v,k;

void dlt(){
	for (int i=1;i<=n;i++){
		if (in[i]==1){
			q.push(i);
			vis[i]=1;
		}
	}
	
	while (!q.empty()){
		int idx=q.front();
		q.pop();
		for (int i=0;i<g[idx].size();i++){
			if (vis[g[idx][i]]==0){
				if (--in[g[idx][i]]==1){
					q.push(g[idx][i]);
					vis[g[idx][i]]=vis[idx]+1;
				}
			}
		}
	}
}

int main(){
	cin>>T;
	while(T--){
		cin>>n>>k;
		for (int i=1;i<=n;i++){
			vis[i]=0;
			g[i].clear();
			in[i]=0;
		}
		
		for (int i=1;i<n;i++){
			cin>>u>>v;
			g[u].push_back(v);
			g[v].push_back(u);
			in[u]++;
			in[v]++;
		}
		
		dlt();
		
		int ans=0;
		for (int i=1;i<=n;i++){
			if (vis[i]>k){
				ans++;
			}
		}
		cout<<ans<<endl;
	}
}

最长回文串

#include<bits/stdc++.h>
using namespace std;
int v[26];
int main()
{
    int n;
    string s;
    cin>>n>>s;
    int cnt = 0;
    int flag = false;
    for(int i = 0;i<n;i++)
    {
        v[s[i]-'a']++;
    }
    for(int i = 0;i<26;i++)
    {
        cnt+=v[i]/2;
        if(v[i]%2==1)
            flag = true;
    }
    cout<<cnt*2+flag;
}

最大中等果实

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	vector<int> a;
	for(int i = 1;i<=n;i++){
		int x;
		cin>>x;
		a.push_back(x);
	}
	sort(a.begin(),a.end());
	int middle = n/2;
	while(k--){
		a[middle]++;
		sort(a.begin(),a.end());
	}
	cout<<a[middle];
	return 0;
}

最糟糕的记者

#include<bits/stdc++.h>
using namespace std;
vector<int> tr[5010];
int in[5010];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
        cin>>a>>b;
		tr[a].push_back(b);
		in[b]++;
	}
	queue<int> q;
	for(int i=1;i<=n;i++)if(in[i]==0)q.push(i);
	int op = 0;
	vector<int> ans;
	while(q.size()){
		if(q.size()>1)op=1;
		int u = q.front();
		q.pop();
		ans.push_back(u);
		for(int son:tr[u]){
			if(--in[son]==0)q.push(son);
		}
	}
	for(int x:ans)cout<<x<<" ";
	cout<<endl;
	cout<<op;
	return 0;
}

游览

#include<bits/stdc++.h>
using namespace std;
vector<int> tr[100010];
int in[100010];
int dp[100010];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        tr[a].push_back(b);
        in[b]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(in[i]==0){
            q.push(i);
            dp[i] = 1;
        }
    }
    while(q.size()){
        int u = q.front();
        q.pop();
        for(int son:tr[u]){
            dp[son] = max(dp[u]+1,dp[son]);
            if(--in[son]==0)q.push(son);
        }
    }
    for(int i=1;i<=n;i++){
        cout<<dp[i]<<endl;
    }
    return 0;
}

五子棋

#include <iostream>
#include <vector>
using namespace std;
const int dir[8][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, -1}, {-1, 1}, {1, 1}, {-1, -1}};
int mod(int x, int m) {
    return (x % m + m) % m;
}
int main() {
    int n, m, t;
    cin >> n >> m >> t;
    t += 1; 
    vector<vector<int>> g(n, vector<int>(m));
    vector<vector<int>> back_up(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            back_up[i][j] = g[i][j] = s[j] - '0';
        }
    }
    while (t-- > 0) {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = back_up[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int a[4] = {1, 1, 1, 1};
                for (int k = 0; k <= 4; k++) {
                    if (g[mod(i + k, n)][j] == 0) {
                        a[0] = 0;
                        break;
                    }
                }
                for (int k = 0; k <= 4; k++) {
                    if (g[i][mod(j + k, m)] == 0) {
                        a[1] = 0;
                        break;
                    }
                }
                for (int k = 0; k <= 4; k++) {
                    if (g[mod(i + k, n)][mod(j + k, m)] == 0) {
                        a[2] = 0;
                        break;
                    }
                }
                for (int k = 0; k <= 4; k++) {
                    if (g[mod(i - k, n)][mod(j + k, m)] == 0) {
                        a[3] = 0;
                        break;
                    }
                }

                for (int k = 0; k < 4; k++) {
                    ans += a[k];
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int cnt = 0;
                for (int k = 0; k < 8; k++) {
                    int ni = mod(i + dir[k][0], n);
                    int nj = mod(j + dir[k][1], m);
                    if (g[ni][nj] == 1) cnt++;
                }
                if (g[i][j] == 1) {
                    if (cnt < 2) back_up[i][j] = 0;
                    else if (cnt <= 3) back_up[i][j] = 1;
                    else back_up[i][j] = 0;
                } else {
                    if (cnt == 3) back_up[i][j] = 1;
                }
            }
        }
        cout << ans << "\n";
    }
    return 0;
}