铺地毯
简单题，就是将所有的地毯数值读入之后然后从第n个地毯开始判断是否覆盖了所需要判断的点code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int x1 , y1;
int x2 , y2;
}a[10005];
int main(void){
int n;
while(cin>>n){
for(int i = 1 ; i <= n ; ++i)
cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
int x , y;
cin>>x>>y;
int ans = -1;
for(int i = n ; i >= 1 ; --i){
if( x >= a[i].x1 && x <= a[i].x1 + a[i].x2 && y >= a[i].y1 && y <= a[i].y2 + a[i].y1){
ans = i;
break;
}
}
cout<<ans<<endl;
}
return 0;
}纪念品分组
还是简单题，要尽可能的多那就只要把大的和小的打包在一起就好了，所以先排序，然后最大的加上最小的如果小于要求的值久打包在一起code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 30005;
bool flag[MAXN] = {0};
int main(void){
int sum;
cin>>sum;
int n;
cin>>n;
int a[MAXN];
for(int i = 1 ; i <= n ; ++i){
scanf("%d", &a[i]);
}
sort(a + 1 , a + n + 1);
int ans = 0;
for(int i = 1 , j = n ; j >= i ;){
if(a[i] + a[j] <= sum){
ans++;
i++;
j--;
}
else{
j--;
ans++;
}
}
cout<<ans<<endl;
return 0;
}校门外的树
这个题目数据量不大，可以直接用差分来做
即给定的每一个区间，左端点减减，右端点后一个点加加，然后求一次前缀和，值为0的即为有树的地方
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10005;
int a[MAXN];
int main(void){
int L , n;
cin>>L>>n;
for(int i = 1 ; i <= n ; ++i){
int l,r;
cin>>l>>r;
a[l]--,a[r+1]++;
}
for(int i = 0 ; i <= L ; ++i)
a[i] += a[i-1];
ll ans = 0;
for(int i = 0 ; i <= L ; ++i)
if(!a[i])
ans++;
cout<<ans<<endl;
return 0;
}然后是数据较大的情况，对于但是
可以用离散化来做
即只记录端点，中间的我们就不要了，最后只要找到前缀和的和是0的区间长度就好了
首先我们用一个数组记录每次的左端点和右端点右边的一个节点，赋值分别为
和
，表示区间的开始和结束，最后还还要加一个0点，赋值为0；
这样按照升序排序，直接将权值累加，当权值加到
的时候，并且目前处理的是区间的开始端点，那么就表示这一个点和上一个区间的结束点就是存在树的点，还有就是最后一个端点和
的距离要额外算一次，避免遗漏
这样子说可能不好理解，表示累加的值，当
累加到1的时候且当前这个端点为
，说明在此之前，
的值为
，且这个点为另一个区间的开始，所以在这个区间的开始和上一个区间的结束这一段，前缀和都为0，即有树
之所以要最后算一个最后一个端点和的距离，就是如果最后一个点没有到
，那么
到最后这个端点的距离都是没有被移除的，即有树
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10005;
struct node{
int pos , val;
bool operator < (const node&b) const{
return pos < b.pos;
}
}a[MAXN<<1];
int main(void){
int L , n;
cin>>L>>n;
for(int i = 1 ; i <= n ; ++i){
int l , r;
cin>>l>>r;
a[i * 2 - 1].pos = l;
a[i * 2 - 1].val = 1;
a[i * 2].pos = r + 1;
a[i * 2].val = -1;
}
a[0].pos = 0 , a[0].val = 0;
sort(a + 1 , a + 2 * n + 1);
int ans = 0 , sum = 0;
for(int i = 1 ; i <= 2 * n ; ++i){
sum += a[i].val;
if(sum == 1 && a[i].val == 1)
ans += a[i].pos - a[i - 1].pos ;
}
ans += L - a[2 * n].pos + 1;
cout<<ans<<endl;
return 0;
}
明明的随机数
这个题目的做法就太多了 ，这里就直接用set过了
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
set<int> s;
int n;
cin>>n;
while(n--){
int k;
cin>>k;
s.insert(k);
}
set<int>::iterator i;
cout<<s.size()<<endl;
for(i = s.begin() ; i !=s.end() ; ++i)
cout<<*i<<" ";
cout<<endl;
return 0;
}拼数
题目很简单，就是按字典序排一下然后比较一下长短不同的怎么排就可以直接输出相同长度的很明显就是直接按字典序排
那么不同的，举个例子
312 31
很明晰31312 大于31231
那么是怎么判断的呢
观察发现两如果是像321 21 这样的毫无疑问就是直接32121这样排
前面这个例子到长度不同的地方都是相同的
所以我们看发生差异的位置，很明显就是短的长度的下一位有差别
即313和312 所以我们只要在排序中特判即可，详细看代码中的cmp函数
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 25;
bool cmp(string a , string b){
for(int i = 0 ; i < a.size() && i < b .size() ; ++i){
if(a[i] != b[i]) return a[i] > b[i];
}
if(a.size() > b.size())
return a[b.size() - 1] < b[0];
else
return b[a.size() - 1] < a[0];
}
int main(void){
string a[MAXN];
int n;
cin>>n;
for(int i = 1 ; i <= n ; ++i)
cin>>a[i];
sort(a + 1 , a + n + 1 , cmp);
for(int i = 1 ; i <= n ; ++i)
cout<<a[i];
cout<<endl;
return 0;
}激光炸弹
二维dp
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5000 + 7;
int dp[MAXN][MAXN];
int main(void){
int n , r;
cin>>n>>r;
for(int i = 1 ; i <= n ; ++i){
int x , y , val;
cin>>x>>y>>val;
dp[x + 1][y + 1] = val;
}
for(int i = 1 ; i < MAXN ; ++i){
for(int j = 1 ; j < MAXN ; ++j){
dp[i][j] = dp[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
}
}
int ans = 0;
for(int i = r ; i < MAXN ; ++i){
for(int j = r ; j <MAXN ; ++j){
ans = max(ans , dp[i][j] - dp[i][j - r] - dp[i - r][j] + dp[i - r][j - r]);
}
}
cout<<ans<<endl;
return 0;
}值周
这个题目就是前面那个校门外的树，一摸一样，唯一的区别就是把L开大了，只能用离散的做法去做
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100000005;
struct node{
int pos , val;
bool operator < (const node&b) const{
return pos < b.pos;
}
}a[MAXN<<1];
int main(void){
int L , n;
cin>>L>>n;
for(int i = 1 ; i <= n ; ++i){
int l , r;
cin>>l>>r;
a[i * 2 - 1].pos = l;
a[i * 2 - 1].val = 1;
a[i * 2].pos = r + 1;
a[i * 2].val = -1;
}
a[0].pos = 0 , a[0].val = 0;
sort(a + 1 , a + 2 * n + 1);
int ans = 0 , sum = 0;
for(int i = 1 ; i <= 2 * n ; ++i){
sum += a[i].val;
if(sum == 1 && a[i].val == 1)
ans += a[i].pos - a[i - 1].pos ;
}
ans += L - a[2 * n].pos + 1;
cout<<ans<<endl;
return 0;
}Selfish Grazing
题目很经典，贪心的策略就是从最右边开始，然后允许反悔，即发现下一个段比这一个段更优，就替换掉他
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 50000 +5;
struct node{
int x , y;
bool operator<(const node&b) const{
if(y == b.y) return x < b.x;
return y > b.y;
}
}a[MAXN];
int main(void){
int n;
cin>>n;
for(int i = 1 ; i <= n ; ++i)
cin>>a[i].x>>a[i].y;
sort(a + 1 , a + n + 1);
int ans = 1;
for(int i = 2 , pos = 1 ; i <= n ; ++i){
if(a[i].y <= a[pos].x){
ans++;
pos = i;
}
else if(a[i].x > a[pos].x) pos = i;
}
cout<<ans<<endl;
return 0;
}切长条
这个题目的策略就是先排序，然后找最先结束的一条，切掉，维护左右区间，然后再找最先结束的再切掉，由此得到的便是最优解，记得每一次判断的时候维护右区间，因为可能出现左区间更后但是右区间更前的段，这个时候就应该把右区间维护过来
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 50000 +5;
struct node{
int x , y;
bool operator<(const node&b) const{
if(x == b.x) return y < b.y;
return x < b.x;
}
}a[MAXN];
int main(void){
int n , k;
cin>>n;
for(int i = 1 ; i <= n ; ++i){
cin>>a[i].x>>k;
a[i].y = a[i].x +k;
}
sort(a + 1 , a + n + 1);
int ans = 1;
for(int i = 2 , l = a[1].x , r = a[1].y; i <=n ; ++i){
if(a[i].x >= r){
ans++;
l = a[i].x;
r = a[i].y;
continue;
}
if(a[i].x < r) r = min(r , a[i].y);
}
cout<<ans<<endl;
return 0;
}「土」巨石滚滚
这个题目的策略也好理解，优先选择能够加稳定性的，在能加稳定性的里面优先选受到破坏值小的，在题目中写的很清楚了，如果承受不了破坏值就不能加后面的稳定性
有一个坑点就是就开来存，
还有就是在比较是否能够存下的时候应该和收到的破化值比较（代码里会标注出来
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 500000 +5;
struct node{
int x,y;
int val;
bool operator<(const node&b) const{
if(val > 0 && b.val > 0) return x < b.x;
if(val < 0 && b.val < 0) return y > b.y;
return val > b.val;
}
}a[MAXN];
int main(void){
int T;
cin>>T;
while(T--){
ll n , sum;
cin>>n>>sum;
for(int i = 1 ; i <= n ; ++i){
cin>>a[i].x>>a[i].y;
a[i].val = a[i].y - a[i].x;
}
sort(a + 1 , a + n + 1);
int flag = 1;
for(int i = 1 ; i <= n ; ++i){
if(a[i].x > sum){ //就是这里比较的时候要和破坏值比较
cout<<"No"<<endl;
flag = 0;
break;
}
sum += a[i].val;
}
if(flag) cout<<"Yes"<<endl;
}
return 0;
}Flip Game
位运算枚举，正面枚举一边，背面枚举一遍取最小的次数即可比较难受的这个题目应该是从pta链接过来的
远古编译器
code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int MAXN = 6;
int a[MAXN] , b[MAXN] , x[MAXN] , c[MAXN];
int ans = INT_MAX;
int num[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
void work(int a[]){
for(x[1] = 0 ; x[1] <= 15 ;++x[1]){
int cnt = num[x[1]];
c[1] = a[1] ^ x[1] ^ (x[1] >> 1) ^ ((x[1] << 1) & 15);
c[2] = a[2] ^ x[1] ;
for(int i = 2 ; i <= 4 ; ++i){
x[i] = c[i - 1];
cnt += num[x[i]];
c[i] = c[i] ^ x[i] ^ (x[i] >> 1) ^((x[i] << 1) & 0xf);
c[i + 1 ] = a[i + 1] ^ x[i];
}
if(!c[4])
ans = min(ans , cnt);
}
}
int main(void){
for(int i = 1 ; i <= 4 ; ++i){
for(int j = 0 ; j < 4 ; ++j){
char s;
scanf(" %c" , &s);
if(s == 'b') a[i] |= 1 << j;
else b[i] |= 1 << j;
}
}
work(a);
memset(c , 0 , sizeof(c));
work(b);
if(ans == INT_MAX) cout<<"Impossible"<<endl;
else cout<<ans<<endl;
return 0;
}Subsequence
尺取code
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
ll a[MAXN] , sum[MAXN];
int main(void){
int T;
cin>>T;
while(T--){
int n , m;
cin>>n>>m;
for(int i = 1 ; i <= n ; ++i)
cin>>a[i];
int ans = n + 1 , sum = 0;
for(int r = 1 , l = 1 ; r <= n+1 ;){
if(sum < m){
sum += a[r];
++r;
}
if(sum >= m ){
ans = min(ans , r - l);
sum -= a[l];
++l;
if(l >= r) break;
}
}
if(ans == n + 1) cout<<"0"<<endl;
else cout<<ans<<endl;
}
return 0;
}
京公网安备 11010502036488号