第一题，找规律只要有4个成双的点就可以构造矩形
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Read sc=new Read();
int t=sc.nextInt();
while(t-->0){
int n=sc.nextInt();
Map<Integer,Integer> map=new HashMap<>();
List<Integer> list=new ArrayList<>();
for(int i=0;i<n;i++){
int tmp=sc.nextInt();
map.put(tmp,map.getOrDefault(tmp,0)+1);
if(map.get(tmp)==2){
list.add(tmp);
map.put(tmp,0);
}
}
if(list.size()<4){
System.out.println("NO");
}else{
System.out.println("YES");
Collections.sort(list);
System.out.println(list.get(0)+" "+ list.get(1)+" "+ list.get(0)+" "+ list.get(list.size()-1)+" "+list.get(list.size()-2)+" "+list.get(1)+" "+ list.get(list.size()-2)+" "+ list.get(list.size()-1));
}
}
}
}
class Read {
BufferedReader bfr=new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer st = new StreamTokenizer(bfr);
public int nextInt() throws IOException {
st.nextToken();
return (int) st.nval;
}
public long nextLong() throws IOException {
st.nextToken();
return (long) st.nval;
}
public String nextLine() throws IOException {;
return bfr.readLine();
}
}
第二题，栈
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Read sc = new Read();
int n = Integer.valueOf(sc.nextLine());
String s = sc.nextLine();
Stack<Integer> stack = new Stack<>();
StringBuilder ans = new StringBuilder();
int id = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
id++;
stack.push(id);
ans.append(id);
} else {
if (stack.isEmpty()) {
System.out.println("-1");
return;
}
ans.append(stack.pop());
}
}
if (!stack.isEmpty()) {
System.out.println("-1");
return;
}
System.out.println(ans.toString());
}
}
class Read {
BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer st = new StreamTokenizer(bfr);
public int nextInt() throws IOException {
st.nextToken();
return (int) st.nval;
}
public String nextLine() throws IOException {
return bfr.readLine();
}
}
第三题，简单迷宫，dfs秒了
using namespace std;
int n,m;
bool f = 0;
char dit[505][505] = {0};
void dfs(int i ,int j)
{
if(dit[i][j] == 'x' || dit[i][j] == '0' || i < 0 || i >= n || j < 0 || j >=m || f==1)
return ;
if(dit[i][j] == 't')
{
f = 1;
return;
}
dit[i][j] = '0';
dfs(i-1,j);dfs(i+1,j);
dfs(i,j+1);dfs(i,j-1);
}
int main()
{
int t;
cin >> t;
while(t--)
{
f = 0;
cin >> n >> m;
for(int i = 0;i < n;i ++)
cin >> dit[i];
for(int i = 0;i < n && f==0;i ++)
{
for(int j = 0;j < m && f == 0;j ++)
{
if(dit[i][j] == 's')
{
dfs(i,j);
if(f)
cout << "YES\n";
else
cout << "NO\n";
}
}
}
}
}
第四题，条件略复杂的模拟，用变量表述当前资源数量、效率、等级、升级所需，模拟题目过程即可
using namespace std;
int main()
{
{
double t, wo = 0, ir = 0, wo_ = 0, ir_ = 0;
long all = 0;
int arr[10010] = { 0 };
cin >> t;
while (t--)
{
if (wo_ <= ir_)
{
if (wo < (wo_ + 1) * 10)
{
wo += wo_ * 0.25 + 1;
all += (wo_ * 0.25 + 1)*100;
}
else if (ir < (wo_ + 1) * 8)
{
ir += ir_ * 0.25 + 1;
all += (ir_ * 0.25 + 1)*100;
}
else
{
wo -= (wo_ + 1) * 10;
ir -= (wo_ + 1) * 8;
wo_ += 1; t++;
}
}
else
{
if (wo < (ir_ + 1) * 8)
{
wo += wo_ * 0.25 + 1;
all += (wo_ * 0.25 + 1)*100;
}
else if (ir < (ir_ + 1) * 10)
{
ir += ir_ * 0.25 + 1;
all += (ir_ * 0.25 + 1)*100;
}
else
{
wo -= (ir_ + 1) * 8;
ir -= (ir_ + 1) * 10;
ir_ += 1; t++;
}
}
}
printf("%.2f",all/100.0);
}
return 0;
}
第五题，排序
#include<algorithm>
#include<set>
#include<map>
#include<cstring>
#define x first
#define y second
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
map<int,int> m;
int n,k;
cin>>n>>k;
for(int i=0;i<k;i++)
{
int b,c;
cin>>b>>c;
m[b]+=c;
}
multiset<int> s;
for(auto x:m){
s.insert((-1)*x.second);
}
int ans=0;
for(int i=0;i<n;i++){
if(s.size()>0){
ans+=*s.begin();
s.erase(s.begin());
}
}
ans*=-1;
cout<<ans<<endl;
}
}
第六题，观察样例的规律，都是往前面加三
#include <vector>
#include<algorithm>
using namespace std;
int main() {
int t;
cin >> t;
while (t--)
{
int x=0;
cin >> x;
if (x == 1||x==3) {
cout << -1 << endl;
continue;
}
if((x-2)%2==0)
{
x-=2;
while(x>0)
{
x-=2;
cout<<"33";
}
cout<<"66";
}
if((x-5)%2==0)
{
x-=5;
while(x>0)
{
x-=2;
cout<<"33";
}
cout<<"36366";
}
cout<<endl;
}
return 0;
}
第七题 ，多重背包问题(模板)
public class Main {
static int n,m,N=2010;
static int dp[][]=new int[N][N];
static int v[]=new int[N],w[]=new int[N],s[]=new int[N];
public static void main(String[] args) throws IOException {
Read sc=new Read();
n=sc.nextInt();
m=sc.nextInt();
for(int i=1;i<=n;i++){
v[i]=sc.nextInt();
w[i]=sc.nextInt();
s[i]=sc.nextInt();
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;j>=k*v[i]&&k<=s[i];k++){
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
}
}
}
System.out.println(dp[n][m]);
}
}
class Read{
StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public int nextInt() throws IOException {
st.nextToken();
return (int)st.nval;
}
}
第八题 根据题目直接暴力
import java.util.*;
public class Main {
static int n, m, q;
static int[][] grass;
static int[][][] plans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] firstLine = br.readLine().split(" ");
n = Integer.parseInt(firstLine[0]);
m = Integer.parseInt(firstLine[1]);
q = Integer.parseInt(firstLine[2]);
grass = new int[n][m];
for (int i = 0; i < n; i++) {
String line = br.readLine();
for (int j = 0; j < m; j++) {
grass[i][j] = line.charAt(j) - '0';
}
}
plans = new int[q][n][m];
for (int k = 0; k < q; k++) {
for (int i = 0; i < n; i++) {
String line = br.readLine();
for (int j = 0; j < m; j++) {
plans[k][i][j] = line.charAt(j) - '0';
}
}
}
int minPlans = Integer.MAX_VALUE;
List<Integer> bestCombination = null;
for (int mask = 0; mask < (1 << q); mask++) {
int[][] combined = new int[n][m];
List<Integer> combination = new ArrayList<>();
for (int k = 0; k < q; k++) {
if ((mask & (1 << k)) != 0) {
combination.add(k + 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
combined[i][j] |= plans[k][i][j];
}
}
}
}
if (isValid(combined)) {
if (combination.size() < minPlans) {
minPlans = combination.size();
bestCombination = new ArrayList<>(combination);
}
}
}
if (minPlans == Integer.MAX_VALUE) {
System.out.println(-1);
} else {
System.out.println(minPlans);
for (int plan : bestCombination) {
System.out.print(plan + " ");
}
System.out.println();
}
}
private static boolean isValid(int[][] combined) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grass[i][j] == 1 && combined[i][j] == 1) {
return false;
}
if (grass[i][j] == 0 && combined[i][j] == 0) {
return false;
}
}
}
return true;
}
}
京公网安备 11010502036488号