三道都没写出来
32 条回复
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
int n;
scanf_s("%d",&n);
vector<int> num;
int tmp;
for (int i = 0; i < n; i++)
{
scanf_s("%d",&tmp);
num.push_back(tmp);
}
int m;
scanf_s("%d",&m);
vector<int> output;
int l;
int r;
int count_h = 0;
for (int c = 0; c < m; c++)
{
scanf_s("%d",&l);
scanf_s("%d", &r);
l--;
r--;
count_h = 0;
for (int i = l; i <= r - 2; i++)
{
if ((num[i] <= num[i]) && (num[i + 1] <= num[i + 2]))
count_h++;
}
output.push_back(count_h);
}
for (int i = 0; i < output.size(); i++)
{
cout << output[i] << endl;
}
return 0;
}第二道……但是还没来得及写完……时间就到了……
第二题 只有80%没超时
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n, m;
vector<int> a;
cin >> n;
for (int i = 0; i < n; i++)
{
int temp;
cin >> temp;
a.push_back(temp);
}
cin >> m;
vector<int> b;
int t = m;
while (m>0)
{
int flag = 0;
int l, r;
int count = 0;
cin >> l >> r;
for (int i = l - 1; i < r - 2; i++)
if (a[i] <= a[i + 1] && a[i + 1] <= a[i + 2])
{
if (flag == 1)
count += 2;
else
count++;
flag = 1;
i++;
}
else flag = 0;
b.push_back(count);
count = 0;
m--;
}
for (int i = 0; i < t; i++)
cout << b[i] << endl;
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sr = new Scanner(System.in);
int n;
List<Integer> a = new ArrayList<Integer>();
int m;
List<Integer> l = new ArrayList<Integer>();
List<Integer> r = new ArrayList<Integer>();
String line;
line = sr.nextLine();
n = Integer.parseInt(line);
String[] ss;
line = sr.nextLine();
ss = line.split(" ");
for (int i = 0; i < n; ++i) {
a.add(Integer.parseInt(ss[i]));
}
line = sr.nextLine();
m = Integer.parseInt(line);
for (int i = 0; i < m; ++i) {
line = sr.nextLine();
ss = line.split(" ");
l.add(Integer.parseInt(ss[0]));
r.add(Integer.parseInt(ss[1]));
}
// 数据采集完毕
for (int i = 0; i < m; ++i) {
System.out.println(checkPoint(a, l.get(i) - 1, r.get(i) - 1));
}
}
static int checkPoint(List<Integer> a, int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) {
if (i + 2 <= right) {
if (a.get(i) <= a.get(i + 1) && a.get(i + 1) <= a.get(i + 2)) {
++sum;
}
}
}
return sum;
}
}我这样写，第二题通过80%，请问剩下的20%为什么没有过？
#include<bits/stdc++.h>
using namespace std;
int main(int argc,char argv){
int n,k;
while(cin>>n>>k){
vector<int> vect;
for(int i=0;i<n;i++){
int temp;
cin>>temp;
vect.push_back(temp);
}
sort(vect.begin(),vect.end());
vector<int> Dp(k,0);
int temp=k-1;
for(int i=0;i<n-1;i++){
for(int j=temp;j-vect[i]>=0;j--){
Dp[j]=max(Dp[j],Dp[j-vect[i]]+vect[i]);
}
}
cout<<Dp[k-1]+vect[n-1]<<endl;
}
return 0;
}这是第一题
#include<bits/stdc++.h>
using namespace std;
int main(int argc,char argv){
int n;
cin>>n;
vector<int> vect;
for(int i=0;i<n;i++){
int temp;
cin>>temp;
vect.push_back(temp);
}
vector<int> dp(n,0);
for(int i=0;i<n-2;i++){
if(vect[i]<=vect[i+1]&&vect[i+1]<=vect[i+2]){
dp[i]=1;
}
}
int m;
cin>>m;
while(m--){
int left,right;
cin>>left>>right;
int count=0;
if(right-left<2){
cout<<"0"<<endl;
}else{
for(int i=left-1;i<=right-3;i++){
if(dp[i]==1){
count++;
}
}
cout<<count<<endl;
}
}
return 0;
}这是第二题
#include <iostream>
#include <stdio.h>
int main(int argc, char** argv)
{int n = 0;
long long t = 0;
std::cin >> n >> t;
int a[n];
for (int i = 0; i< n; i++)
{std::cin >> a[i];
}
// Sort a[]
for (int it1 = 0; it1 < n; it1 ++)
{for (int it2 = it1 + 1; it2 < n; it2 ++)
{if (a[it1] > a[it2])
{int temp = a[it1];
a[it1] = a[it2];
a[it2] = temp;
}
}
}
// Core
long long sum = 0;
for (int j = 0; j < n; j++)
{sum += a[j];
if (sum >= t)
{if (j == 0)
break;
else if (sum - a[j] < t)
{sum -= a[j];
sum += a[n - 1];
break;
}
}
}
std::cout << sum;
return 0;
}
第一题
#include <iostream>
#include <stdio.h>
int main(int argc, char** argv)
{long n = 0;
long m = 0;
// n
std::cin >> n;
int a[n];
for (int i = 0; i < n; i ++)
{std::cin >> a[i];
}
std::cout << "\n";
// m
std::cin >> m;
int r[m][2];
for (int i = 0; i < m; i ++)
{for (int j = 0; j < 2; j++)
std::cin >> r[i][j];
}
//
for (int i = 0; i < m; i ++)
{std::cout << r[i][0] << " " << r[i][1] << std::endl;
}
// Cal
int cnt = 0;
for (int i = 0; i < m; i ++)
{int div = r[i][1] - r[i][0];
if (div < 2)
cnt = 0;
else
{for (int j = r[i][0] - 1; j < r[i][1] - 2; j ++)
{if (a[j] <= a[j + 1] && a[j + 1] <= a[j + 2])
cnt++;
}
}
std::cout << cnt << std::endl;
cnt = 0;
}
return 0;
}
第二题
第一题题解: 因为尽可能取大,所以从大到小排序.然后用DP来做.
代码如下:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()){
int n = cin.nextInt();
int t = cin.nextInt();
int[] a = new int[n+1];
for(int i=1;i<=n;i++){
a[i] = cin.nextInt();
}
//从大到小排序-插入排序 (为了和dp保持一致,从第二位开始排序)
int j = 0;
for(int i=2;i<=n;i++){
int temp = a[i];
j = i-1;
for(;j>0 && a[j]<temp;j--){
a[j+1] = a[j];
}
a[j+1] = temp;
}
int[][] dp = new int[n+1][t+1];
for(int i=1;i<=n;i++){
for(j=1;j<=t;j++){
if (i>=1 && j>a[i]) {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-a[i]]+a[i]);
}else if(j>0){
dp[i][j] = Math.max(dp[i-1][j], a[i]);
}
}
}
System.out.println(dp[n][t]);
}
}
}如发现问题,麻烦指出.
第三题的代码。
#include <iostream>
#include <vector>
using namespace std;
struct Edge
{
int s;
int e;
};
class Graph
{
private:
vector<vector<int> > head;
public:
Graph(int n)
{
for(int i=0; i<n; i++)
{
vector<int> vertex;
vertex.push_back(i);
head.push_back(vertex);
}
}
int getN()
{
return head.size();
}
vector<Edge> getEdge()
{
vector<Edge> res;
for(int i=0; i<head.size(); i++)
{
int s = head[i][0];
for(int j=1; j<head[i].size(); j++)
{
int e = head[i][j];
Edge t = Edge{s,e};
int tag = 0;
for(int k=0; k<res.size(); k++)
if((res[k].s==t.s&&res[k].e==t.e) || (res[k].s==t.e&&res[k].e==t.s))
tag = 1;
if(tag == 0)
res.push_back(t);
}
}
return res;
}
void addEdge(int u,int v)
{
head[u].push_back(v);
head[v].push_back(u);
}
void delEdge(int u,int v)
{
for(int i=0; i<head[u].size(); i++)
if(head[u][i] == v)
head[u].erase(head[u].begin()+i);
for(int i=0; i<head[v].size(); i++)
if(head[v][i] == u)
head[v].erase(head[v].begin()+i);
}
void DFS(int u,int& vc)
{
int n = head.size();
int* tag = new int[n];
for(int i=0; i<n; i++)
tag[i] = 0;
vc++;
tag[u] = 1;
for(int i=1; i<head[u].size(); i++)
visit(head[u][i],vc,tag);
}
void visit(int u,int &vc,int tag[])
{
vc++;
tag[u] = 1;
for(int i=1; i<head[u].size(); i++)
if(tag[head[u][i]] == 0)
visit(head[u][i],vc,tag);
}
};
int main()
{
int n;
cin >> n;
Graph g = Graph(n);
int* s = new int[n-1]; //边的两端
int* e = new int[n-1];
for(int i=0; i<n-1; i++)
{
cin >> s[i] >> e[i];
g.addEdge(s[i],e[i]);
}
delete[] s;
delete[] e;
int res = 0;
//挨个删除一条边
vector<Edge> all = g.getEdge();
for(int i=0; i<all.size(); i++)
{
Graph o = Graph(g.getN()); //保留原始图g,在复制图o上删除操作
vector<Edge> all = g.getEdge();
for(int i=0; i<all.size(); i++)
o.addEdge(all[i].s,all[i].e);
o.delEdge(all[i].s,all[i].e);
int ovc = 0; //计算删除一条边后，图两个联通分量其中一个联通分量中的顶点数
o.DFS(0,ovc);
if(ovc >= 2 && n-ovc >= 2)
res = res + 8*(ovc-1)*(n-ovc-1);
}
cout << res << endl;
return 0;
}反正显示已完全通过测试数据
package test;
import java.util.Arrays;
import java.util.Scanner;
public class test360 {
public static void main(String[] args) {
int n,t,sum=0;
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
n=sc.nextInt();
t=sc.nextInt();
int [] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i]=sc.nextInt();
}
Arrays.sort(arr);
for (int i = 0; i < n-1; i++) {
sum=sum+arr[i];
if(sum>t)
{
sum=sum+arr[n-1];
break;
}
}
System.out.println(sum);
}
sc.close();
}
}
添加回复
isaimawang
@ 赛码网
533869549