F：
签到题，ifelse一下就行了。。。。我写复杂了。。。。。。。
#include<bits/stdc++.h>
using namespace std;
void solved(){
string s1,s2;
cin>>s1>>s2;
if(s1 == "elephant" && s2 == "tiger"){
cout<<"tiangou yiwusuoyou"<<endl;return ;
}else if(s2 == "elephant" && s1 == "tiger"){
cout<<"tiangou txdy"<<endl;return ;
}
if(s1 == "tiger" && s2 == "cat"){
cout<<"tiangou yiwusuoyou"<<endl;return ;
}else if(s2 == "tiger" && s1 == "cat"){
cout<<"tiangou txdy"<<endl;return ;
}
if(s1 == "cat" && s2 == "mouse"){
cout<<"tiangou yiwusuoyou"<<endl;return ;
}else if(s2 == "cat" && s1 == "mouse"){
cout<<"tiangou txdy"<<endl;return ;
}
if(s1 == "mouse" && s2 == "elephant"){
cout<<"tiangou yiwusuoyou"<<endl;return ;
}else if(s2 == "mouse" && s1 == "elephant"){
cout<<"tiangou txdy"<<endl;return ;
}
cout<<"tiangou yiwusuoyou"<<endl;return ;
}
int main(){
solved();
return 0;
} G：
签到题，贪心选择要画的时间最少的科目，排序一下，然后一个一个去选就行了。(要开ll才行)
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
typedef long long int ll;
ll a[maxn];
void solved(){
ll n,m;scanf("%lld%lld",&n,&m);
for(ll i = 1; i <= n; i++)scanf("%lld",&a[i]);
sort(a + 1,a + 1 + n);
ll ans = 0;
for(ll i = 1; i <= n; i++){
if(m >= a[i]){
m-=a[i];
ans++;
}else break;
}
printf("%lld\n",ans);
}
int main(){
solved();
return 0;
} B：
问题可以简化为：给你一些数，满足这些数最大值与最小值差<=k，并长度最长。
为了方便处理，我们先排序，然后枚举每一个数的起始位置，然后二分出它最大值位置(满足差<=k)，然后用他们的长度更新答案。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn = 2e5 + 10;
ll a[maxn],dis[maxn];
void solved(){
int t;
for(scanf("%d",&t);t;t--){
ll n,k;cin>>n>>k;
for(int i = 1; i <= n; i++)cin>>a[i];
sort(a + 1,a + 1 + n);
int ans = 0;
for(int i = 1; i <= n; i++){
int v = k + a[i];
int pos = lower_bound(a + 1,a + 1 + n,v) - a;
if(a[pos] == v){
ans = max(ans,pos - i + 1);
}else{
ans = max(ans,pos - i);
}
}
cout<<ans<<endl;
}
}
int main(){
solved();
return 0;
} H：
并查集的裸题了。。不过太久没写并查集导致很多细节没处理好。思路很简单，先将c=1的a，b并在同一个集合，然后检查c=0，如果发现a，b在同一个集合就会产生矛盾。cin超时要用scanf，由于每次读入两个点，所以maxn要开两倍，a,b<=1e9，所以还需要离散化一下，大概就是这些坑了。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
typedef long long int ll;
struct node{
int a,b,c;
node(){}
node(int a,int b,int c):a(a),b(b),c(c){};
}ans[maxn];
int res[maxn << 1];
int f[maxn << 1];
int find(int x){
return f[x] == x? x : f[x] = find(f[x]);
}
void solved(){
int t;
for(scanf("%d",&t);t;t--){
int n; scanf("%d",&n);
int cnt = 0;
for(int i = 1; i <= n * 2 ; i++)f[i] = i;
for(int i = 1; i <= n; i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
res[++cnt] = x;
res[++cnt] = y;
ans[i] = {x,y,z};
}
sort(res + 1,res + 1 + cnt);
int len = unique(res + 1,res + 1 + cnt) - (res + 1);
bool flag = true;
for(int i = 1; i <= n; i++){
int u = ans[i].a;
int v = ans[i].b;
u = lower_bound(res + 1, res + 1 + len,u) - res;
v = lower_bound(res + 1, res + 1 + len,v) - res;
if(ans[i].c == 1){
int fa = find(u);
int fb = find(v);
if(fa != fb)f[fa] = fb;
}else{
if(find(u) == find(v))flag = false;
}
}
if(flag)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
int main(){
solved();
return 0;
}D：
区间修改，区间求和，所以需要用到前缀和与差分，由于是二维的，所以前缀和与差分也需要二维的，可以先对所有区间修改差分一下，然后求一个和，得出每个数原来的值，再求一次前缀和实现O(1)区间和查询。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e3 + 10;
typedef long long int ll;
ll a[maxn][maxn];
void solved(){
int n,m,k,q;
scanf("%d%d%d%d",&n,&m,&k,&q);
while(k--){
ll x1,x2,y1,y2;scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
a[x1][y1]++;
a[x2 + 1][y2 + 1]++;
a[x1][y2 + 1]--;
a[x2 + 1][y1]--;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
a[i][j] += a[i][j - 1];
}
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
a[i][j] += a[i - 1][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
a[i][j] += a[i - 1][j];
}
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
a[i][j] += a[i][j - 1];
}
}
for(int i = 1; i <= q; i++){
ll x1,x2,y1,y2;scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
cout<<a[x2][y2] + a[x1 - 1][y1 - 1] - a[x1 - 1][y2] - a[x2][y1 - 1]<<endl;
}
}
int main(){
solved();
return 0;
} J题
sum1求aj的前缀和，sum2求aj^2的前缀和，将公式展开直接O(n)就可以做完了。
不过取模有亿点点麻烦，我是把所有能取的地方全部取了才过的，还是减法取模的时候要+mod才行，防止产生负数
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
typedef long long int ll;
ll mod = 1e9 + 7;
ll a[maxn];
ll sum1[maxn],sum2[maxn];
void solved(){
int n;scanf("%d",&n);
for(int i = 1; i <= n; i++){
scanf("%lld",&a[i]);
sum1[i] = (sum1[i - 1] + a[i]) % mod;
sum2[i] = (sum2[i - 1] + a[i] * a[i] % mod) %mod;
}
ll ans = 0;
for(int i = 1; i <= n; i++){
ans += (((n - i) * a[i] % mod * a[i] % mod) %mod - (2 * a[i] % mod * (sum1[n] - sum1[i] + mod) %mod) %mod + (sum2[n] - sum2[i] + mod)%mod)%mod;
}
printf("%lld\n",ans%mod);
}
int main(){
solved();
return 0;
} C题
题意就是要你包围住这个联通块。
你可以想象一个大矩形，我们要把外面的包起来，里面的不要包，并且边界没有#,所以我们可以直接从起点(1,1)bfs，把那个矩形外围全部标记一下，矩形里面的不用管，然后遍历一下迷宫如果它是#我们就找他的四个方向，如果满足某个方向已经被标记过，我们我们可以把它改成*。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
char s[maxn][maxn];
bool vis[maxn][maxn];
int dir[][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int n,m;
struct node{
int x,y;
node(){}
node(int a,int b):x(a),y(b){}
};
void bfs(int x,int y){
queue<node>st;
st.push(node(x,y));
while(!st.empty()){
node cur = st.front();st.pop();
for(int i = 0 ; i < 4; i++){
int fx = cur.x + dir[i][0];
int fy = cur.y + dir[i][1];
if(fx < 1 || fy < 1 || fx > n || fy > m)continue;
if(s[fx][fy] != '#' && !vis[fx][fy]){
st.push(node(fx,fy));
vis[fx][fy] = true;
}
}
}
}
void solved(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf(" %c",&s[i][j]);
bfs(1,1);
//for(int i = 1; i <= n; i++)
// for(int j = 1; j <= m; j++)
// if(vis[i][j])cout<<i<<" "<<j<<endl;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(s[i][j] == '#'){
for(int k = 0; k < 4; k++){
int fx = i + dir[k][0];
int fy = j + dir[k][1];
if(vis[fx][fy] && s[fx][fy] == '.'){
s[fx][fy] = '*';
}
}
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
printf("%c",s[i][j]);
}
cout<<endl;
}
}
int main(){
solved();
return 0;
} 
京公网安备 11010502036488号