A题
题意：两个人，假设A叫做纪少，B 叫做赵XX；
然后纪少会藏一个灯笼之后，赵XX 再拿一个纪少的灯笼，与自己的灯笼配对，
问题是，这个配对的灯笼总亮度，纪少想尽可能的小，赵XX 与之相反
思路：暴力，因为数据范围很小，n^2不会超时，所以先找到配对最大的那个灯笼，标记下标，找到除此之外最大 的配对亮度
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include <cassert>
#define ll long long
using namespace std;
void clear(unsigned char *pta, int size )
{
while(size>0)
{
*pta++ = 0;
size --;
}
}
struct node
{
unsigned long long x, y, z;
ll step ;
};
node p[100000];
ll cmp(ll a, ll b){
return a>b;
}
int main()
{
vector<ll> ar,arr,br,brr;
int n, m ;cin >>n>>m;
for(int i=0;i<n;i++){
ll kk;cin >>kk;
//if(kk<0) arr.push_back(kk);
ar.push_back(kk);
}
ll ma=-9e18+1;
for(int i=0;i<m;i++){
ll kk;cin >>kk;
// if(kk<0) brr.push_back(kk);
br.push_back(kk);
}ll x , y ;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(ar[i]*br[j]>ma){
ma = ar[i]*br[j];
x = i;
y = j;
}
}
}ma=-9e18+1;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i== x)continue;
if(ar[i]*br[j]>ma){
ma = ar[i]*br[j];
}
}
}cout<<ma<<endl;} B题
题意：给一个数，问你是否可以用图形封闭的数量表示出来，能就表示出来，不能就-1（0-9图形封闭的数是0，4,6,8,9，除了8是2个封闭图形，都是1）
思路：首先看范围，发现是1e18,也就是说极端情况都是8的情况下，也就是32，也就说n>32 的都表示不了，然后剩下的2的倍数就全输出8，奇数就先输出0（4,6,9），在全输出8；
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include <cassert>
#define ll long long
using namespace std;
void clear(unsigned char *pta, int size )
{
while(size>0)
{
*pta++ = 0;
size --;
}
}
struct node
{
unsigned long long x, y, z;
ll step ;
};
node p[100000];
ll cmp(ll a, ll b){
return a>b;
}
int main()
{
ll n;cin >>n;
if(n>36)cout<<"-1";
else {
if(n%2){
cout<<4;
for(int i=0;i<(n-1)/2;i++)cout<<"8";
}
else if(n%2==0)
for(int i=0;i<n/2;i++)cout<<"8";
}
cout<<endl;
} C题
题意：问你在区间翻转的条件下，找到最长上升子序列的长度
思路：板子题，看懂题，上网找一个板子就过了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int maxn = 2200;
int maxm = 2200;
int n, a[20000], dp[2001][2001], b[20000];
int ans, ansl, ansr, l, r, cnt;
int al[2001][2001], ar[2001][2001];
int solve()
{
for(int i = 0; i <= cnt; i++)
dp[0][i] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= cnt; j++)
{
dp[i][j] = dp[i - 1][j];
al[i][j] = al[i - 1][j];//al记录翻转的左端点
ar[i][j] = ar[i - 1][j];//al记录翻转的左端点
if(a[i] == b[j])
{
dp[i][j] = dp[i - 1][j] + 1;
if(l == j && !al[i][j])//如果当前的j就是b开始翻转的左端点,更新记录
al[i][j] = i;
if(r == j)//当前的j是b翻转的右端点,记录更新
ar[i][j] = i;
}
if(dp[i][j - 1] > dp[i][j])//如果答案有更新就要更新答案
{
dp[i][j] = dp[i][j - 1];
al[i][j] = al[i][j - 1];
ar[i][j] = ar[i][j - 1];
}
}
}
return dp[n][cnt];
}
int main()
{
//int t;
//scanf("%d", &t);
cin >>n;
for(int i=1;i<=n;i++)cin >>a[i];
cnt = 0;
for(int i = 0; i <= 9; i++)
b[++cnt] = i;
ansl = ansr = l = r = 1;
ans = solve();
for(int i = 0; i <= 9; i++) //枚举翻转b数组的每一段
{
for(int j = i + 1; j <= 9; j++)
{
cnt = 0;
for(int k = 0; k <= i; k++)
b[++cnt] = k;
l = cnt+1;//左端点
for(int k = j; k >= i; k--)//只翻转i~j区间的数
b[++cnt] = k;
r = cnt;//右端点
for(int k = j; k <= 9; k++)
b[++cnt] = k;
/* for(int i=1; i<=cnt; i++)
printf("%d ",b[i]);
printf("\n");*/
int tmp = solve();
if(ans < tmp)//不断更新答案 && al[n][cnt] && ar[n][cnt]
{
ans = tmp;
}
}
}
printf("%d\n", ans);
return 0;
} E题
题意就是循环三次后，能否回去
思路：暴力，用数组存后，三重嵌套查询；
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include <cassert>
#define ll long long
using namespace std;
void clear(unsigned char *pta, int size )
{
while(size>0)
{
*pta++ = 0;
size --;
}
}
struct node
{
unsigned long long x, y, z;
ll step ;
};
node p[100000];
ll cmp(ll a, ll b){
return a>b;
}
int ar[1000000];
ll br[1000000];
int main()
{
int n;cin >>n;
for(int i=1;i<=n;i++) {
cin >>ar[i];
}
for(int i=1;i<=n;i++){
if(ar[ar[ar[i]]]==i){
return cout<<"YES"<<endl,0;
}
}cout<<"NO"<<endl;
} F题
题意：n 个仓鼠，k种笼子型号。问你最多能装多少仓鼠，并输出笼子型号
思路：暴力，遍历一遍找能存最多仓鼠的笼子即可
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include <cassert>
#define ll long long
using namespace std;
void clear(unsigned char *pta, int size )
{
while(size>0)
{
*pta++ = 0;
size --;
}
}
struct node
{
unsigned long long x, y, z;
ll step ;
};
node p[100000];
ll cmp(ll a, ll b){
return a>b;
}
int ar[1000000];
ll br[1000000];
ll mi =0x7f7f7f ;
int main()
{
ll n ;int k;
cin >>n;cin >>k;
long long ma=1e18+1 , cnt =0 ,pos=0;
for(int i=1;i<=k;i++){
long long num;
cin >>num;
if(ma>n%num){
ma = n%num;
pos = i;
cnt = n/num;
}
}
cout<<pos<<" "<<cnt<<endl;
} G题
题意：一堆时区的人想打比赛，每个临近的时区只差一个小时，问在第一时区第几小时的时候，参赛人数最多。
思路：可以说是尺取法，或者叫做暴力，位移时区，具体看代码就懂了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
map<pair<int, int>, int> mp;
int arr[10000000];
int main()
{
int n;cin >>n;
for(int i=1;i<= n;i++){
cin>>arr[i%n];//使时区变为一个循环
}
int s ,f ;cin >>s>>f;int sum =0;
int pos =0 ;
for(int i =s ;i<f;i++) sum +=arr[i%n];int len = sum ;
for(int i=1;i<n;i++){
int l = (s- i + n)%n;
int r = (f- i + n)%n;
sum +=arr[l];
sum -=arr[r];
if(sum >len){
len = sum ;
pos = i;
}
}
cout<<pos +1 <<endl;
return 0;
} H题
题意：秀恩爱，给你两个字符串，问你用最小代价下，是这两个字符串相等（相等就是让两个字符可以互相转换）
思路：并查集模板题，然后用两个数组存一下转换的字符就行了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
map<pair<int, int>, int> mp;
const int maxn = 1e6;
int arr[10000000];
int l[1000000]={0}, r[maxn];
int find(int x ){
if(arr[x]!=x)arr[x] = find(arr[x]);
return arr[x];
}
void bin(int a , int b){
int x ,y;
x = find(a);
y = find(b);
if(x!=y){
arr[x]=y;
}
}
int main()
{
int n;cin >>n;
string s1 ,s2 ;cin >>s1>>s2;
int len =0;
for(int i=0;i<n;i++){
arr[s1[i]-'a'+1] = s1[i]-'a'+1;
arr[s2[i]-'a'+1] = s2[i]-'a'+1;
}for(int i=0;i<n;i++){
if(arr[find(s1[i]-'a'+1)]!=arr[find(s2[i]-'a'+1)]){
bin(s1[i]-'a'+1,s2[i]-'a'+1);
l[len] = s1[i]-'a'+1;
r[len++] = s2[i]-'a'+1;
}
}
cout<<len <<endl;
for(int i=0;i<len;i++){
cout<<char(l[i]+'a'-1)<<" "<<char(r[i]+'a'-1)<<endl;
}
return 0;
}
京公网安备 11010502036488号