题目过于简单,就不在线讲题了,看这个题解即可。
A: 签到题1,记录个id和val,然后再结构体排序,然后用两根指针,一个在前一个在后边输出边移动输出即可,直接计算位置也可以。
#include <bits/stdc++.h>
using namespace std;
struct node{
int val,id;
friend bool operator<(const node &a,const node &b){
return a.val<b.val;
}
}a[110];
int n;
int main()
{
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i].val,a[i].id=i;
sort(a+1,a+n+1);
for(int i=1; i<=n/2; i++){
cout<<a[i].id<<" "<<a[n-i+1].id<<endl;
}
}
B:签到题2,判断一个括号序列是否合法,典型的栈的应用,见代码。注意下(([[这种trick即可。
string line;
stack <char> s;
bool isok(char a, char b){
if(a == '(' && b == ')') return true;
else if(a == '[' && b == ']') return true;
else return false;
}
int main()
{
int T; scanf("%d%*c", &T);
while(T--){
while(!s.empty()) s.pop();
char ch;
while((ch = getchar()) != '\n'){
if(ch == '(' || ch == '['){
s.push(ch);
}
else if(ch == ')' || ch == ']'){
if(s.empty()) s.push(ch);
else if(ch == ']'){
if(s.top() != '['){
}
else{
s.pop();
}
}
else if(ch == ')'){
if(s.top() != '('){
}
else{
s.pop();
}
}
}
}
if(s.empty()){
printf("Yes\n");
}
else{
printf("No\n");
}
}
return 0;
}
C:给了n个数,问你能否找到另外一个数使得这n+1个数构成等差数列,有无数个输出-1,没有输出0,否则先输出可以找到的数的个数,然后输出这n个数,一个最简单的想法就是先排序,排序之后我们去找出现的公差的的个数的最大值,发现这个值是>=2的话,显然是无解的,因为存在两种很大跨度的公差添加一个数去平衡,显然是办不到的,接下来就是分类讨论一下,这个值为1, 0的情况了,逻辑严密这题就很好过了。我的代码比较丑,供参考。(PS:反正我没有一发过,我好菜啊)
#include <bits/stdc++.h>
const int maxn = 1e5+10;
int a[maxn];
int b[maxn];
map<int,int>mp;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
if(n == 1){
printf("-1\n");
continue;
}
sort(a+1,a+n+1);
memset(b,0,sizeof(b));
mp.clear();
for(int i = 1; i < n; i++) b[i] = a[i+1] - a[i];
for(int i = 1; i < n; i++) mp[b[i]]++;
int ans = 0;
for(map<int,int>::iterator it = mp.begin(); it != mp.end(); it++) ans = max(ans,it->second);
int add = 1e8;
for(int i = 1; i < n; i++){
if(mp[b[i]] == ans){
add = min(add,b[i]);
}
}
for(int i = 2; i <= n; i++){
if((a[i] - a[i-1]) != add) cnt++;
}
if(cnt >= 2){
printf("0\n");
continue;
}
else if(cnt == 0){
if(a[1] == a[2]){
printf("1\n");
printf("%d\n",a[1]);
}
else if(n >2 ){
printf("2\n");
printf("%d %d\n",a[1]-add,a[n]+add);
}
else if(n == 2){
if((a[2] - a[1])%2==1){
printf("2\n");
printf("%d %d\n",a[1]-add,a[n]+add);
}
else{
printf("3\n");
printf("%d %d %d\n",a[1]-add,(a[1]+a[2])/2,a[2]+add);
}
}
}
else if(cnt == 1){
int temp = 0;
bool flag2 = 1;
for(int i = 1; i <= n; i++){
if(a[i] + add != a[i+1]){
temp = a[i] + add;
if(a[i+1] != temp + add){
flag2 = 0;
}
break;
}
}
if(temp < a[1] || temp > a[n] || flag2 == 0){
printf("0\n");
}
else{
printf("1\n");
printf("%d\n",temp);
}
}
}
return 0;
}
D:这个问题就很有趣了,其实它比C还简单。题意是给定一个集合,该集合由1,2,3….2n组成,n是一个整数。问该集合中有趣子集的数目,答案mod1e9+7。x的子集合有趣定义为,该子集中至少有两个数,a和b,b是a的倍数且a是集合中最小的元素。
分析:考虑一下枚举一个最小元素,那么比它大的元素的个数显然为(2*n / a-1)。这其中的元素有选和不选两种,但是不能全部不选。接下来是所有大于最小元素的元素并且不是最小元素倍数的数,可以随便选,于是公式就很显然了。不嫌麻烦,也可以跑一个快速幂。
int f[2001];
int main()
{
f[0] = 1;
REP2(i, 1, 2000) f[i] = (f[i - 1] << 1) % mod;
int n, tt, ks = 0;
scanf("%d", &tt);
while(tt--){
scanf("%d", &n);
int ans = 0;
REP2(i, 1, n){
ans += (1LL * ((f[2 * n / i - 1] - 1) % mod) * 1LL * (f[2 * n - i - 2 * n / i + 1] % mod)) % mod;
ans %= mod;
}
if(ans < 0) ans += mod;
printf("Case %d: %d\n", ++ks, ans);
}
return 0;
}
E:题意是给出一个长度为n的序列c[i],每次操作可以删去一个回文子串,求将整个序列删除完需要的最少操作数,n<=500。
分析:区间dp,记dp[i][j]为删完[i,j]这一段的最少操作次数,一种转移是枚举一个k,将这一段分为[i,k]和[k+1,j]两段分别删,那么有dp[i][j]=min(dp[i][k]+dp[k+1][j]),另一种转移是如果满足c[i]==c[j],那么在删完[i+1,j-1]的最后一步时可以顺带把c[i]和c[j]一起删掉,那么有dp[i][j]=min(dp[i-1][j+1]),复杂度O(n^3)
可以用记忆化搜索的方式写,代码1:
int n, c[510], dp[510][510];
void dfs(int l, int r){
if(dp[l][r] < INF) return;
if(r <= l){
dp[l][r] = 1;
return ;
}
int tl = l, tr = r;
while(tl < tr && c[tl] == c[tr]){
tl++; tr--;
dfs(tl, tr);
dp[l][r] = min(dp[l][r], dp[tl][tr]);
}
REP1(k, l, r){
dfs(l, k);
dfs(k + 1, r);
dp[l][r] = min(dp[l][k] + dp[k + 1][r], dp[l][r]);
}
}
int main()
{
cin >> n;
REP2(i, 1, n) cin >> c[i];
REP1(i, 0, 510){
REP1(j, 0, 510){
dp[i][j] = INF;
}
}
dfs(1, n);
cout << dp[1][n] << endl;
return 0;
}
也可以像昨天讲的区间DP的方式转移,显然递归常数比较大,个人还是推荐这种方式。
代码2:
int n, c[510], dp[510][510];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> c[i];
for(int i = 1; i < 510; i++){
for(int j = 1; j < 510; j++){
dp[i][j] = INF;
}
}
for(int i = 1; i <= n; i++) dp[i][i] = 1;
for(int len = 2; len <= n; len++){
for(int i = 1; i + len - 1 <= n; i++){
if(c[i] == c[i + len - 1])
{
if(len == 2) dp[i][i + 1] = 1;
else dp[i][i + len - 1] = min(dp[i + 1][i + len - 2], dp[i][i + len - 1]);
}
else{
dp[i][i + len - 1] = INF;
}
for(int j = i; j < i + len - 1; j++){
dp[i][i + len - 1] = min(dp[i][i + len - 1], dp[i][j] + dp[j + 1][i + len - 1]);
}
}
}
cout << dp[1][n] << endl;
}