首页 > 其他分享 >NEERC2009解题报告

NEERC2009解题报告

时间：2023-03-01 15:48:11浏览次数：53  
标签：报告 int MAXM ++ 解题 NEERC2009 字符串 include fin

B. Business Center

有 \(m\) 个电梯，每个电梯有两个权值 \(a,b\)，初始在第 \(0\) 层。你可以选择一个电梯，进行恰好 \(n\) 次操作，每次要么升高 \(a\) 要么下降 \(b\)。要求最终在第一层以上且尽可能低。

对于每个电梯 \(a,b\)，考虑进行几次上几次下。由于要求在第一层以上，所以上的层数大于下的层数，即 \(ax>b(n-x)\)。解一下不等式即可。

By Waterloo Black

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

int n,m,best,u,d;
int main() {
  freopen("business.in","r",stdin);
  freopen("business.out","w",stdout);
  best=3000;
  cin >> n >> m;
  for(int i=0;i<m;i++){
    cin>>u>>d;
    best=min(best,(u*n-1)%(u+d)+1);
  }
  cout<<best<<endl;

}

D. Database

有一个表格，每个格子为一个字符串，问是否存在两个行 \(x,y\) 和两个列 \(i,j\)，使得 \((x,i)=(y,i)\) 且 \((x,j)=(y,j)\)。\(n\le 10000,m\le 10\)。

由于列数很少，显然可以枚举两个列，然后判断是否有两个行在这两列上的取值相等。可以使用字符串哈希进行比较，map 进行维护。

By dnkywin

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

ifstream fin ("database.in");
ofstream fout ("database.out");

typedef unsigned long long ull;

vector<ull> mat[10100];

int main()
{
  int n, m;
  fin >> n >> m;
  string s;
  getline(fin, s);
  for (int i = 0; i < n; i++) {
    getline(fin, s);
    ull h = 0;
    vector<ull> hashes;
    for (int j = 0; j < s.size(); j++) {
      if (s[j] == ',') {
        hashes.push_back(h);
        h = 0;
      } else {
        h = h * 137 + s[j];
      }
    }
    hashes.push_back(h);
    mat[i] = hashes;
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < i; j++) {
      map<pair<ull, ull>, int> f;
      for (int k = 0; k < n; k++) {
        auto t = make_pair(mat[k][i], mat[k][j]);
        if (f.count(t)) {
          fout << "NO" << endl;
          fout << f[t] + 1 << " " << k + 1 << "\n";
          fout << j + 1 << " " << i + 1 << "\n";
          return 0;
        }
        f[t] = k;
      }
    }
  }
  fout << "YES" << endl;
}

或者可以不哈希，直接用 string 和 pair 自带的比较函数扔进 map 里。

By DemiGuo

using namespace std;

const int maxn=20000+10;
const int maxm = 15;
int n, m;
string str, word[maxn][maxm];
map<pair<string,string>, int> ha;

int main()  {
    freopen("database.in", "r", stdin);
    freopen("database.out", "w", stdout);
    scanf("%d%d\n", &n, &m);
    for (int i = 1; i <= n; i ++)  {
        getline(cin, str);
        str = str + ",";
        int len = str.length();
        int c = 0;
        int last = 0;
        for (int j = 0; j < len; j ++)
            if (str[j] == ',')  {
                c ++;
                word[i][c] = str.substr(last, j - last);
                last = j + 1;
                // printf("(%d,%d)=", i,c);
                // cout << word[i][c] << endl;
            }
    }
    for (int c = 1; c <= m; c ++)
        for (int d = c + 1; d <= m; d ++) {
            ha.clear();
            for (int i = 1; i <= n; i ++)  {
                pair<string, string> cur = make_pair(word[i][c], word[i][d]);
                if (ha.count(cur))  {
                    printf("NO\n");
                    printf("%d %d\n", ha[cur], i);
                    printf("%d %d\n", c, d);
                    return 0;
                }
                ha[cur] = i;
            }
        }
    printf("YES\n");
    return 0;
}

F. Funny Language

题意：定义一个字符串能生成的字符串为，选择其中若干个字符重新排列得到的字符串。给定 \(m\) 个字符串，构造 \(n\) 个字符串，使得这 \(n\) 个字符串不能与 \(m\) 个给定的重复，且可以被这 \(m\) 个字符串中尽量多的生成。

一个显然的结论是，若选了某个字符串，其中的每个子串被生成的次数都不会少于这个原串，所以可以先选一个字符的串，然后在逐步加字符，一步一步考虑。可以使用类似 Dijkstra 的做法来一步步扩展，每次选当前被生成次数最多的字符串拓展，直到确定完 \(n\) 个合法的字符串。

By dnkywin

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <fstream>
#include <queue>

using namespace std;
const int MAXM = 1100;

ifstream fin ("funny.in");
ofstream fout ("funny.out");

int N, M;
string s[MAXM];
int distro[MAXM][26];
int d[26];

priority_queue <pair <int, string> > pq;
vector <string> res;

void add (string x)
{
    for (int i = 0; i < 26; i++)
        d[i] = 0;
    for (int i = 0; i < x.length(); i++)
        d[x[i]-'A']++;

    int tot = 0;
    for (int i = 0; i < M; i++)
    {
        bool bad = false;
        for (int j = 0; j < 26; j++)
        {
            if (distro[i][j] < d[j])
            {
                bad = true;
                break;
            }
        }
        if (!bad)
            tot++;
    }

    pq.push (make_pair (tot, x));
}

int main()
{
    fin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        fin >> s[i];

        for (int j = 0; j < 26; j++)
            distro[i][j] = 0;
        for (int j = 0; j < s[i].length(); j++)
            distro[i][s[i][j]-'A']++;
    }

    for (int i = 0; i < 26; i++)
    {
        string S = "";
        S += (char) ('A' + i);
        add (S);
    }

    while (res.size() < N)
    {
        string tval = pq.top().second;
        //cout << pq.top().first << " " << tval << endl;
        pq.pop();


        for (int i = 0; i < 26; i++)
            add (tval + (char) ('A' + i));

        bool bad = false;
        for (int i = 0; i < M; i++)
            if (tval == s[i])
                bad = true;
        if (bad)
            continue;

        res.push_back (tval);
    }

    for (int i = 0; i < N; i++)
        fout << res[i] << "\n";
}

H. Headshot

题意：一个环形排列的 01 串，有一个指针随机指到了一个位置，已知目前在 \(0\)，你可以选择移到下一个位置，也可以选择随机一个位置，问哪个方案选到 \(1\) 的概率更高/相等。

考虑分别计算概率：往后移一位取到 \(1\) 的概率，其为 \(01\) 的个数与 \(0\) 的个数之比；随机去选一位的概率为 \(1\) 的个数与串长的比。分数的比较可以移项转换为乘法比较。

By UH Counting Stars

#include <bits/stdc++.h>

#define int long long

using namespace std;



int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    freopen("headshot.in", "r", stdin);
    freopen("headshot.out", "w", stdout);

    string cad;
    cin >> cad;

    int N = cad.size();

    int p1 = 0;
    int t1 = 0;

    int p2 = 0;
    int t2 = N;

    for(int i = 0 ; i < N ; i++)
    {
    	if(cad[i] == '0')
    	{
    		t1++;
    		if(cad[(i+1)%N] == '1')p1++;
    	}
    	else
    	{
    		p2++;
    	}
    }

    if(p1*t2 < p2*t1)
    {
    	cout << "SHOOT" << '\n';
    }
    if(p1*t2 == p2*t1)
    {
    	cout << "EQUAL" << '\n';
    }
    if(p1*t2 > p2*t1)
    {
    	cout << "ROTATE" << '\n';
    }

    return 0;
}

J. Java Certification

题意：有一个考试，一共 \(n\) 道题，分为 \(m\) 个板块，你一共答对了 \(k\) 道题。给定每个板块你答对的题目的占比（百分比，取整方式为，小于 \(0.5\) 舍弃，大于 \(0.5\) 进一，等于 \(0.5\) 取相邻两个整数中偶数的那个），求每个板块的题数和你答错的题数。如果有多解，求每个板块题目数量极差最小的解。

显然是一个 DP 题。

做法一

令 \(f[i][j][k][l]\) 表示考虑前 \(i\) 个板块，用了 \(j\) 道题，答错了 \(k\) 道题，板块题数的最小值为 \(l\) 时，最大值最小为多少。可以使用刷表法进行转移。一个必需的优化为，预处理每个百分比可能的题数-错误题数二元组，转移时只需要枚举二元组而不需要现计算。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-7;
int a[15],f[11][105][105][105];
struct node {
	int j,k,l;
} pre[11][105][105][105];
int calc(int a,int b) {
	double tmp=a*100.0/b;
	int x=floor(tmp+eps);
	if(tmp-eps>=x+0.5) return ceil(tmp);
	else if(abs(tmp-(x+0.5))<=eps) {
		if(x%2==0) return floor(tmp);
		else return ceil(tmp);
	}
	else return floor(tmp);
}
void print(int i,int j,int k,int l) {
	if(i==0) return;
	print(i-1,pre[i][j][k][l].j,pre[i][j][k][l].k,pre[i][j][k][l].l);
	cout<<k-pre[i][j][k][l].k<<" "<<j-pre[i][j][k][l].j<<endl;
}
int main() {
	freopen("javacert.in","r",stdin);
	freopen("javacert.out","w",stdout);
	int w,n,m;
	cin>>w>>n>>m;
	w=n-w;
	for(int i=1;i<=m;i++)
		cin>>a[i];
	memset(f,0x3f,sizeof(f));
	f[0][0][0][n]=0;
	for(int i=0;i<m;i++) {
		vector<pair<int,int> > ok;
		for(int j=1;j<=n;j++)
			for(int k=0;k<=min(j,w);k++)
				if(calc(j-k,j)==a[i+1])
					ok.push_back({j,k});
		for(int j=i;j<n;j++)
			for(int k=0;k<=min(j,w);k++)
				for(int l=0;l<=n;l++) {
					if(f[i][j][k][l]>1e9) continue;
					for(auto [jj,kk]:ok) {
						if(j+jj>n||k+kk>w) continue;
						int tmp=max(f[i][j][k][l],jj);
						if(tmp<f[i+1][j+jj][k+kk][min(l,jj)]) {
							f[i+1][j+jj][k+kk][min(l,jj)]=tmp;
							pre[i+1][j+jj][k+kk][min(l,jj)]={j,k,l};
						}
					}
				}
	}
	int ans=1e9,minl=0;
	for(int l=1;l<=n;l++)
		if(f[m][n][w][l]-l<ans)
			minl=l,ans=f[m][n][w][l]-l;
	print(m,n,w,minl);
	return 0;
}

做法二

考虑钦定下界，DP 最小的上界，此时 DP 可以减少一维，重复 \(n\) 次即可。具体地，\(f[i][j][k]\) 表示前 \(i\) 个板块，\(j\) 道题，\(k\) 道正确，板块题数最大值最小是多少。转移时钦定板块题数大于等于某个值即可，总复杂度相同，但由于 DP 状态减少，实现上更清爽，空间也更优。

By dnkywin

using namespace std;
typedef long long ll;
const int MAXN = 102;
const int MAXM = 11;

ifstream fin ("javacert.in");
ofstream fout ("javacert.out");

int K, N, M;
int dp[MAXN][MAXN][MAXM]; // [i] questions correct out of [j], [k]-th prob, smallest max
int prev[MAXN][MAXN][MAXM];
vector <pair <int, int> > pposs[MAXM];

int res;
pair <int, int> answer[MAXM];

int getp (int num, int den)
{
    int t = (100 * num + den / 2) / den;
    if (2 * t * den == 200 * num + den && t % 2 == 1)
        --t;
    return t;
}

int solve (int lo)
{
    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXN; j++)
            for (int k = 0; k < MAXM; k++)
                dp[i][j][k] = 1000;

    dp[0][0][0] = 0;
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j <= K; j++)
            for (int k = 0; k <= N; k++)
            {
                for (int l = 0; l < pposs[i].size(); l++)
                {
                    if (pposs[i][l].second < lo) continue;
                    int x = pposs[i][l].first, y = pposs[i][l].second;

                    if (j + x > K || k + y > N)
                        break;

                    if (dp[j+x][k+y][i+1] > max (y, dp[j][k][i]))
                    {
                        dp[j+x][k+y][i+1] = max (y, dp[j][k][i]);
                        prev[j+x][k+y][i+1] = l;
                    }
                }
            }
    }

    //cout << lo << " " << dp[K][N][M] << "\n";
    if (dp[K][N][M] < 1000)
        return dp[K][N][M] - lo;
    return -1;
}

int main()
{
    fin >> K >> N >> M;
    for (int i = 0; i < M; i++)
    {
        pposs[i].clear();
        int x; fin >> x;

        for (int j = 1; j <= 100; j++)
            for (int k = 0; k <= j; k++)
            {
                if (getp (k, j) == x)
                {
                    //cout << i << " " << k << " " << j << "\n";
                    pposs[i].push_back (make_pair (k, j));
                }
            }
    }

    res = 100;
    for (int i = N / M; i >= 1; i--)
    {
        int t = solve (i);
        if (t < res && t != -1)
        {
            res = t;

            int ck = K, cn = N, cm = M;
            while (cm)
            {
                --cm;
                int x = pposs[cm][prev[ck][cn][cm+1]].first;
                int y = pposs[cm][prev[ck][cn][cm+1]].second;
                answer[cm] = make_pair (x, y);
                ck -= x;
                cn -= y;
            }
        }
    }

    for (int i = 0; i < M; i++)
        fout << answer[i].second - answer[i].first << " " << answer[i].second << "\n";
    return 0;
}

标签：报告,int,MAXM,++,解题,NEERC2009,字符串,include,fin
From： https://www.cnblogs.com/cxm1024/p/17168456.html

相关文章

  • EDU-CFR-115-Div-2解题报告
    赛时AC3道，补题做出来一道A.ComputerGame\(Problem\)有一个\(2\timesn\)的01矩阵，1为障碍，你要从\((1,1)\)走到\((2,n)\)，每一步只能向右、上、下、右上、右下走，问......
  • EDU-CFR-116-Div-2解题报告
    比赛传送门做出来五道题。A.ABBalance{%noteinfono-iconproblem%}给你一个只含有a和b的字符串，问怎样通过修改尽可能少的字符，使得ab的数量和ba的数量相......
  • EDU-CFR-138解题报告
    比赛传送门A.CowardlyRooks题意：有一个\(n\timesn\)的棋盘，有\(m\)个位置上有车，保证互不攻击。问是否能将一个车移动一次使得仍然互不攻击。稍加思考可得，如果\(......
  • EDU-CFR-143解题报告
    A.TwoTowers题意：有两个积木塔，由红色/蓝色积木组成，你每次可以将一个塔的塔顶放到另一个塔上，问任意次操作后能否使得两座塔都是红蓝相间。可以将一个塔全部转移到另一......
  • 数据分析报告2
     用电预测：importpandasaspdimportmatplotlib.pyplotaspltdf_normal=pd.read_csv("C:/Users/admin/Documents/WeChatFiles/wxid_b0fz4hqogenr22/FileStorage/Fil......
  • 今日报告-09
    今日打卡所花时间(包括上课)：7h代码量（行）：300发表博客：4篇（不包括本篇）了解到的知识点：今天复习了一下JAVA的一些基础知识，并且看了许多网课教程，对Servlet有了更深的认识.主要......
  • 今日报告
    总结一下：忙碌且迷茫的一天代码时间（包括上课）：5h代码量（行）：200行（主要在写Android程序，还是个半成品）博客数量（篇）：3篇了解到的相关知识点：1、有关Github的相关知识，学习了如何不用......
  • 今日报告
    packagecom.test.jdbc;importjava.sql.Connection;importjava.sql.DriverManager;importjava.sql.PreparedStatement;importjava.sql.ResultSet;importjava.......
  • 省选备战报告 第零辑 分块与根号平衡
    本笔记仅仅记录重点思路，详细解题过程请参阅原题题解难度从低到高为NÄIVE：有效思考时间少于十分钟EASY：能够完全独立得出MEDIUMEASY：需要题解提供关键思路跨越MEDIUM：需......
  • 日程报告8
    代码时间（包括上课）：6h代码量（行）：180博客数（篇）：3 今天实现了昨天的课堂测试基础版（是的，昨天的任务今天刚刚做完T_T），最大的收获就是了解到了spilt函数的存在对文件的操作也进行了......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99