题意：给我 n个值他们的取值范围为\([a,b]\),用给了区间范围\([c,d]\),问这个n个值的总和可能在\([c,d]\)之间？
分析：这个明显是判读两个区间\([n*a,n*b]、[c,d]\)是否相交的问题？我们可分类讨论连个区间是否相交，其实我们要做的判读就是 确定这两个集合一定不相交，那么剩余的情况两个集合有交点的
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
#define ll long long
const int mxn = 2e6;
int main()
{
/* fre(); */
int t;
scanf("%d", &t);
while(t--)
{
int n, a, b, c, d;
scanf("%d %d %d %d %d", &n, &a, &b, &c, &d);
int x1 = a - b, x2 = a + b;
x1 *= n, x2 *= n;
int y1 = c - d, y2 = c + d;
/* cout << x1 << " " << x2 << endl; */
/* cout << y1 << " " << y2 << endl; */
/* cout << x1*n << " " << x2*n << endl; */
if(x2 < y1 || x1 > y2)
printf("NO\n");
else
printf("YES\n");
}
return 0;
}
题意：给我一个长度为n的序列，序列中存在“极大值”概念：如果当前元素大于两边的元素，在区间的开头和结尾处不存在“极大值”，现在让我们在这个序列中选一个长度为n的连续的子序列，它包含的“极大值”的数量是多少？，最后在这个最大数量上+1，就是答案
分析：用类似“前缀数组”进行预处理“极大值”的数量
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
#define ll long long
const int mxn = 2e6;
int ar[mxn], pref[mxn];
int main()
{
/* fre(); */
int t;
scanf("%d", &t);
while(t--)
{
int n, k;
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i ++)
scanf("%d", &ar[i]);
for(int i = 2; i <= n - 1; i ++)
{
pref[i] = pref[i - 1];
if(ar[i] > ar[i - 1] && ar[i] > ar[i + 1])
pref[i] ++;
}
int mx = 0, l = 1;
for(int i = 1; i < n - k + 2; i ++)
{
if(mx < pref[i + k - 2] - pref[i])
{
mx = pref[i + k - 2] - pref[i];
l = i;
}
}
printf("%d %d\n", mx + 1, l);
}
return 0;
}
分析：这题的题意真恶心，不过就是一个水题，我们通过??的方法构造一个长度为6的序列ar，我假设刚开始序列中已经有一个数1了「* * 1 * * 」， 代表需要我们填充数，请看下面的模拟操作
即1的后面填充数字2,所以序列ar变为了「* * 1 2 * *」即：在2的后面进行填充数字3，那么ar序列变为：「* * 1 2 3 *」，即：在3的后面填数字4,那么ar数组为「* * 1 2 3 4」#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
#define ll long long
const int mxn = 2e6;
int ar[mxn], pos[mxn];
int main()
{
/* fre(); */
int t;
scanf("%d", &t);
while(t--)
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
{
scanf("%d", &ar[i]);
pos[ar[i]] = i;
}
int flag = 1;
int last = n + 1;
int tem;
for(int i = 1; i <= n; )
{
tem = pos[i];
for(int j = pos[i]; j < last; j ++)
{
if( ar[j] == i)
i ++;
else
{
flag = 0;
break;
}
}
if(! flag)
break;
last = tem;
}
if(flag)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
题意：给我我们一个n位数，每个位数上的数字由7个灯管组成，如上图，有些灯管是开着的，有些灯管是闭着的，如最上面??的那幅图表示的是\([1,9]\),问我现在可把其中灭者的一些灯管打开k个，之后这个n位数最大可以变为多大，输出出来它
分析：这明显是一个动态规划问题，不过这个思路就是很难想了，首先我们先预处理每个位置到数变成1-9之间的消耗的打开灯管的次数，然后我们定义\(dp[i][j] = 1\)表示把从第i个数到最后一个数变的合理恰好要打开j个灯管，等于0则表示不行，我们从n到1逆向枚举j的值，这我样我在最需要看dp[1][k] 是否为1，就知道是否有答案了，又因为对于每一个位置i，我们可以把把那个位置上的数变成 1～9之间的任意一个数，而变成其中一个一些数，变成一个不同的数消耗的开关次数可能不同，也可能相同，对与每一个i位置要变成1～9之间的数我们从小到大枚举，这样有多个合理值的时候我们只标记最大的那个。
最后再逆项令 i从1到n找合理最大标记
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
const int mxn = 3005;
string s[10] = { "1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011" };
int cost[mxn][10];
int dp[mxn][mxn];
int main()
{
ios::sync_with_stdio(false);
/* fre(); */
int n, k;
cin >> n >> k;
string st;
for(int i = 1; i <= n; i ++)
{
cin >> st;
for(int j = 0; j < 10; j ++)
{
for(int k = 0; k < 9; k ++)
{
if(st[k] == ‘1‘ && s[j][k] == ‘0‘)
{
cost[i][j] = -1;
break;
}
if(st[k] == ‘0‘ && s[j][k] == ‘1‘)
cost[i][j] ++;
}
}
}
dp[n + 1][0] = 1;
for(int i = n; i >= 1; i --)
{
for(int j = 0; j <= 9; j ++)
{
if(cost[i][j] == -1) continue;
for(int l = 0; l <= k; l ++)
{
if(dp[i + 1][l] == 1)
dp[i][l + cost[i][j]] = 1;
}
}
}
string ans;
for(int i = 1; i <= n; i ++)
{
for(int j = 9; j >= 0; j --)
{
if(cost[i][j] == -1) continue;
if(cost[i][j] > k) continue;
if(dp[i + 1][k - cost[i][j]] != 1) continue;
ans += j + ‘0‘;
k -= cost[i][j];
break;
}
if(ans == "")
{
ans += "-1";
break;
}
}
cout << ans << endl;
return 0;
}
Codeforces Round #637 (Div. 2) - Thanks, Ivan Belonogov!
原文：https://www.cnblogs.com/lql-nyist/p/12775400.html