花了2.5小时把部分题目重新写了一遍(数字接龙的DFS调了接近80min才调出来)

这里的答案不是全AC的，有问题的我标出来了

C题：好数

题目：一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位 · · · ）上的数字是奇数，偶数位（十位、千位、十万位 · · · ）上的数字是偶数，我们就称之为“好数”。给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。

输入格式：一个整数 N。

输出格式：一个整数代表答案。

样例输入：

24

样例输出：

7

评测：https://www.dotcpp.com/oj/problem3209.html：

AC

#include<bits/stdc++.h>
using namespace std;
bool good(int x)
{
	for(int i=1;x;i++)
	{
		int tmp=x%10;
		x/=10;
		if(tmp%2!=i%2) return 0;
	}
	return 1;
}
int main()
{
	int n,res=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		if(good(i)) res++;
	printf("%d",res);
	return 0;
}

D题：R格式

题目描述：小蓝最近在研究一种浮点数的表示方法：R 格式。对于一个大于 0 的浮点数 d，可以用 R 格式的整数来表示。给定一个转换参数 n，将浮点数转换为 R格式整数的做法是：

1. 将浮点数乘以 2n;

2. 四舍五入到最接近的整数。

输入格式：一行输入一个整数 n 和一个浮点数 d，分别表示转换参数，和待转换的浮点数。

输出格式：输出一行表示答案：d 用 R 格式表示出来的值。

样例输入：

2 3.14

样例输出：

13

【样例说明】

3.14 × 22 = 12.56，四舍五入后为 13。

【评测用例规模与约定】

对于 50% 的评测用例：1 ≤ n ≤ 10，1 ≤ 将 d 视为字符串时的长度 ≤ 15。

对于 100% 的评测用例：1 ≤ n ≤ 1000，1 ≤ 将 d 视为字符串时的长度≤ 1024；保证 d 是小数，即包含小数点。

评测：https://www.dotcpp.com/oj/problem3210.html

WA(#12WA,95%AC)：没有处理连续进位

#include<bits/stdc++.h>
using namespace std;
const int N=5000;
string str;
int n,v[N],st;
void print_full()
{
	for(int i=1000;i>=0;i--) cout<<v[i];
}
int main()
{
	cin>>n>>str;
	for(int i=0,j=str.length()-2;i<str.length();++i,--j)
	{
		if(str[i]!='.') v[j]=str[i]-'0';
		else
		{
			++j;
			st=j;
		}
	}
	//下面开始高精度计算
	while(n--)
	{
		for(int i=0;i<=2500;++i) v[i]*=2;
		for(int i=0;i<=2500;++i)
		{
			v[i+1]+=v[i]/10;
			v[i]%=10;
		}
	}
	bool flag=0;
	for(int i=2100;i>st;--i)
	{
	    if(flag==0&&v[i]==0) continue;
	    flag=1;
		cout<<v[i];
	}
	if(v[st-1]>=5) cout<<v[st]+1;
	else cout<<v[st];
	//print_full();
	return 0;
}

E题：宝石组合

题目描述：在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了N 枚宝石，第 i 枚宝石的 “闪亮度” 属性值为 Hi，小蓝将会从这 N 枚宝石中选出三枚进行组合，组合之后的精美程度 S 可以用以下公式来衡量：

其中 LCM 表示的是最小公倍数函数。小蓝想要使得三枚宝石组合后的精美程度 S 尽可能的高，请你帮他找出精美程度最高的方案。如果存在多个方案 S 值相同，优先选择按照 H 值升序排列后字典序最小的方案。

输入格式：第一行包含一个整数 N 表示宝石个数。第二行包含 N 个整数表示 N 个宝石的 “闪亮度”。

输出格式：输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。

样例输入：

5
1 2 3 4 9

样例输出：

1 2 3

【评测用例规模与约定】

对于 30% 的评测用例：3 ≤ N ≤ 100，1 ≤ Hi ≤ 1000。

对于 60% 的评测用例：3 ≤ N ≤ 2000。

对于 100% 的评测用例：3 ≤ N ≤ 105，1 ≤ Hi ≤ 105。

评测：https://www.dotcpp.com/oj/problem3211.html

WA(AC5%)：贪心思路错误

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int prime[N],idx=2,n,q[N],ans[5],num;
bool st[N];
void init()
{
	prime[1]=1;
	for(int i=2;i<=1e5+5;i++)
	{
		if(!st[i]) prime[idx++]=i;
		for(int j=2;prime[j]<(1e5+5)/i;j++)
		{
			st[prime[j]*i]=1;
			if(i%prime[j]==0) break;
		}
	}
	idx--; 
}
bool check_in(int x)
{
	int l=1,r=idx;
	while(l<r)
	{
		int mid=l+r>>1;
		if(prime[mid]>=x) r=mid;
		else l=mid+1;
	}
	if(prime[l]==x) return 1;
	else return 0;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&q[i]);
	init();
	sort(q+1,q+1+n);
	for(int i=n;i>=1;i--)
	{
		if(check_in(q[i])) ans[++num]=q[i];
		if(num==3) break;
	}
	printf("%d %d %d",ans[3],ans[2],ans[1]);
	return 0;
}

F题：数字接龙

题目描述：小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为N × N 的格子棋盘上展开，其中每一个格子处都有着一个 0 . . . K − 1 之间的整数。游戏规则如下：

\1. 从左上角 (0, 0) 处出发，目标是到达右下角 (N − 1, N − 1) 处的格子，每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。

\2. 对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . . 。

\3. 途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。

\4. 路径中不可以出现交叉的线路。例如之前有从 (0, 0) 移动到 (1, 1)，那么再从 (1, 0) 移动到 (0, 1) 线路就会交叉。

为了方便表示，我们对可以行进的所有八个方向进行了数字编号，如下图2 所示；因此行进路径可以用一个包含 0 . . . 7 之间的数字字符串表示，如下图 1是一个迷宫示例，它所对应的答案就是：41255214。

现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径，输出字典序最小的那一个；如果不存在任何一条路径，则输出 −1。

输入格式：第一行包含两个整数 N、K。接下来输入 N 行，每行 N 个整数表示棋盘格子上的数字。

输出格式：输出一行表示答案。如果存在答案输出路径，否则输出 −1。

样例输入：

3 3
0 2 0
1 1 1
2 0 2

样例输出：

41255214

【样例说明】行进路径如图 1 所示。 【评测用例规模与约定】对于 80% 的评测用例：1 ≤ N ≤ 5。对于 100% 的评测用例：1 ≤ N ≤ 10，1 ≤ K ≤ 10

评测：https://www.dotcpp.com/oj/problem3212.html

AC

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int res,g[N][N],f[N][N],fx[N][N],dp[N*N],qx=0,qy=0,x0,y0,n,k;
const int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
void dfs(int x, int y, int p0, int zt)
{
    if (res == 1) return;
    if (x == x0 && y == y0 && p0 == n * n - 1)
	{
        res = 1;
        for (int i = 0; i < n * n - 1; ++i) cout<<dp[i];
        return;
    }
    if(zt==k-1) zt=-1;
    for(int i=0;i<8;++i)
	{
        int ax=x+dx[i];
        int ay=y+dy[i];
        if (f[ax][ay] || g[ax][ay] != zt + 1 || x < 0 || y < 0 || x >= n || y >= n) continue;
        //下面处理交叉的情况 
        if (i==1&&(fx[x][y+1]==7||fx[x-1][y]==3)) continue;
        if (i==3&&(fx[x][y+1]==5||fx[x+1][y]==1)) continue;
        if (i==5&&(fx[x][y-1]==3||fx[x+1][y]==7)) continue;
        if (i==7&&(fx[x][y-1]==1||fx[x-1][y]==5)) continue;
        f[ax][ay]=1,fx[x][y]=i,dp[p0]=i;
        dfs(ax,ay,p0+1,g[ax][ay]);
        dp[p0]=-1,fx[x][y]=-1,f[ax][ay]=0;
    }
}
int main()
{
    cin >> n >> k;
    x0 = n - 1, y0 = n - 1;
    for (int i = 0; i < n; ++i)
    	for (int j = 0; j < n; ++j)
        	cin >> g[i][j];
    f[qx][qy] = 1;
    dfs(qx, qy, 0, 0);
    if (!res) cout << -1 << endl;
    return 0;
}

G题：爬山

题目描述：小明这天在参加公司团建，团建项目是爬山。在 x 轴上从左到右一共有 n座山，第 i 座山的高度为 hi。他们需要从左到右依次爬过所有的山，需要花费的体力值为 S = Σni=1hi。

然而小明偷偷学了魔法，可以降低一些山的高度。他掌握两种魔法，第一种魔法可以将高度为 H 的山的高度变为 ⌊√H⌋，可以使用 P 次；第二种魔法可以将高度为 H 的山的高度变为 ⌊H/2⌋，可以使用 Q 次。并且对于每座山可以按任意顺序多次释放这两种魔法。

小明想合理规划在哪些山使用魔法，使得爬山花费的体力值最少。请问最优情况下需要花费的体力值是多少？

输入格式：输入共两行。

第一行为三个整数 n，P，Q。

第二行为 n 个整数 h1，h2，. . . ，hn。

输出格式：输出共一行，一个整数代表答案。

输出格式：

4 1 1
4 5 6 49

输出格式：

18

【样例说明】将第四座山变为 ⌊√49⌋ = 7，然后再将第四座山变为 ⌊7/2⌋ = 3。体力值为 4 + 5 + 6 + 3 = 18。

【评测用例规模与约定】

对于 20% 的评测用例，保证 n ≤ 8，P = 0。

对于 100% 的评测用例，保证 n ≤ 100000，0 ≤ P ≤ n，0 ≤ Q ≤ n，0 ≤ hi ≤ 100000。

评测：https://www.dotcpp.com/oj/problem3213.html

WA(#3#5#7 WA,AC75%):有待debug，未找到原因，贪心思路错误

#include<bits/stdc++.h>
using namespace std;
struct H
{
	int h,sub1,sub2,sub;
	bool operator < (const H &W) const 
	{
		return sub<W.sub;
	}
};
priority_queue<H>que;
H create(int x)
{
	int sub1=x-sqrt(x);
	int sub2=x-x/2;
	int sub=min(sub1,sub2);
	return {x,sub1,sub2,sub};
}
int main()
{
	int n,p,q;
	//数据读入 
	scanf("%d%d%d",&n,&p,&q);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		que.push(create(x));
	}
	//开始贪心
	while(!que.empty())
	{
		if(p==0&&q==0) break;
		auto x=que.top();
		que.pop();
		if(x.sub1>=x.sub2&&p>0)
		{
			p--;
			que.push(create(sqrt(x.h)));
		}
		else if(q>0)
		{
			q--;
			que.push(create(x.h/2));
		}
		else
		{
			p--;
			que.push(create(sqrt(x.h)));
		}
	}
	int res=0;
	while(!que.empty())
	{
		auto x=que.top();
		que.pop();
		res+=x.h;
	}
	printf("%d",res);
	return 0;
}

H题的话，考场上我用DP做的，n^3的一个代码，肯定过不了。听说正解是线段树，我也不高兴写了......