M. Gitignore
Your git project (you don't need to be familiar with git to solve this problem) has some files that should be ignored from synchronizing. You need to calculate the minimum number of lines needed for gitignore.
Formally, your project is a folder. A folder can have files and sub folders. There are no empty folders (i.e. folders without any files or sub folders inside). Initially, the git software will synchronize all the files in your project. However, you can specify some files and folders in the settings (which is called gitignore) to exclude them from synchronizing. For each line in gitignore, you can specify either a file or all the files in a folder. You can not ignore the whole project folder (i.e. an empty line in gitignore).
You are given paths for all the files in the project and whether they should be ignored or shouldn't. Your task is to calculate the minimum number of lines for gitignore.
map暴力硬写就完了,要大胆暴力
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
void save_the_people() {
int n,m;
cin>>n>>m;
int ans{n};
map<string,int> mp;
string s1[n],s2[m];
for(int i{0};i<n;i++){
cin>>s1[i];
}
for(int i{0};i<m;i++){
cin>>s2[i];
}
for(int i{0};i<m;i++){
int p=s2[i].size();
string ss="";
for(int j{0};j<p;j++){
ss+=s2[i][j];
if(s2[i][j]=='/'){
mp[ss]=1;
}
}
}
for(int i{0};i<n;i++){
int p=s1[i].size();
string ss="";
for(int j{0};j<p;j++){
ss+=s1[i][j];
if(s1[i][j]=='/'){
if(mp[ss]==0) { mp[ss] = 2; }
else if(mp[ss]==2){
ans--;
break;
}}
}
}
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t{1};
cin>>t;
while(t--) {
save_the_people();
}
}
J. Let's Play Jigsaw Puzzles!
模拟,先找出左上角那个,然后一次排出一排,剩下的再依次以这一排位基排列;
注意使用快速读取;
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
const int N=1005;
int n[N*N],s[N*N],w[N*N],e[N*N];
int a[N][N];
void save_the_people() {
int m;
cin>>m;
for(int i{1};i<=m*m;i++){
cin>>n[i]>>s[i]>>w[i]>>e[i];
if(n[i]==-1&&w[i]==-1)a[1][1]=i;
}
for (int i{2};i<=m;i++) a[1][i]=e[a[1][i-1]];
for (int i{2};i<=m;i++)
for (int j{1};j<=m;j++) a[i][j]=s[a[i-1][j]];
for(int i{1};i<=m;i++){
for(int j{1};j<=m;j++){
cout<<a[i][j]<<" \n"[j==m];
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t{1};
//cin>>t;
while(t--) {
save_the_people();
}
}
C. Engineer Artem
Artem is building a new robot. He has a matrix a consisting of n rows and m columns. The cell located on the i-th row from the top and the j-th column from the left has a value ai,j written in it.
If two adjacent cells contain the same value, the robot will break. A matrix is called good if no two adjacent cells contain the same value, where two cells are called adjacent if they share a side.
Artem wants to increment the values in some cells by one to make a good.
More formally, find a good matrix b that satisfies the following condition —
For all valid (i,j), either bi,j=ai,j or bi,j=ai,j+1.
For the constraints of this problem, it can be shown that such a matrix b
always exists. If there are several such tables, you can output any of them. Please note that you do not have to minimize the number of increments.
奇偶构造即可;
构造题注意使用逆运算,位分解,直接构造等;
本题直接构造即可
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
void save_the_people() {
int n,m;
cin>>n>>m;
vector<vector<int>> a(n+1,vector<int> (m+1)),b(n+1,vector<int> (m+1));
for(int i{1};i<=n;i++){
for(int j{1};j<=m;j++){
cin>>a[i][j];
if((i+j)%2==0&&a[i][j]%2==0)a[i][j]++;
if((i+j)%2==1&&a[i][j]%2==1)a[i][j]++;
}
}
for(int i{1};i<=n;i++){
for(int j{1};j<=m;j++){
cout<<a[i][j]<<' ';
}cout<<"\n";
}
}
signed main() {
int t{1};
cin>>t;
while(t--) {
save_the_people();
}
}
E. Another MEX Problem
题目链接:https://codeforces.com/contest/1870/problem/E
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
const int maxn = 1e6 + 7;
const int N = 2e5 + 5;
#define mem(a,x) memset(a,x,sizeof(a));
void save_the_people(){
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++) {
cin>>a[i];
}
int dp[n+1][n+1];
mem(dp,0);
dp[0][0] = 1;
int mex[n+1];
mem(mex,-1);
int cnt[n+1];
for(int i=1;i<=n;i++) {
mem(cnt,0);
int cur = 0;
for(int k=0;k<=n;k++) {
dp[i][k] = dp[i-1][k];
}
for(int j=i;j!=0;j--) {
cnt[a[j]]++;
bool flag = 0;
while(cnt[cur]) {
cur++;
flag = 1;
}
if(flag && cur != mex[j]) {
for(int k=0;k<=n;k++) {
if(dp[j-1][k]) {
dp[i][k^cur] = 1;
}
}
}
mex[j] = cur;
}
}
for(int k=n;k>=0;k--) {
if(dp[n][k]) {
cout<<k;
return;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tcase{1};cin>>tcase;
while(tcase--) {
save_the_people();
cout<<'\n';
}
}
D. Prefix Purchase
题目链接:https://codeforces.com/contest/1870/problem/D
即找出能构造出的字典序最大的数组
从后往前取min,传递最小值,
从前往后取大构造
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
const int N=1e9+5;
void newnew(){
int n;
cin >> n;
vector<int> c(n);
for (int i = 0; i < n; i++) {
std::cin >> c[i];
}
for (int i = n - 2; i >= 0; i--) {
c[i] =min(c[i], c[i + 1]);
}
int k;
cin >> k;
vector<int> a(n);
int t = k;
for (int i = 0; i < n; i++) {
int v = c[i] - (i ? c[i - 1] : 0);
if (v > 0) {
t =min(t, k / v);
}
k -= t * v;
a[i] = t;
cout << a[i] << " \n"[i == n - 1];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _=1;cin>>_;
while(_--){
newnew();
}
}
非常弹的球
刚上高一的森森为了学好物理，买了一个“非常弹”的球。虽然说是非常弹的球，其实也就是一般的弹力球而已。森森玩了一会儿弹力球后突然想到，假如他在地上用力弹球，球最远能弹到多远去呢？他不太会，你能帮他解决吗？当然为了刚学习物理的森森，我们对环境做一些简化：
假设森森是一个质点，以森森为原点设立坐标轴，则森森位于(0, 0)点。
小球质量为w/100 千克（kg），重力加速度为9.8米/秒平方（m/s^2 ）。
森森在地上用力弹球的过程可简化为球从(0, 0)点以某个森森选择的角度ang (0<ang<π/2) 向第一象限抛出，抛出时假设动能为1000 焦耳（J）。
小球在空中仅受重力作用，球纵坐标为0时可视作落地，落地时损失p%动能并反弹。
地面可视为刚体，忽略小球形状、空气阻力及摩擦阻力等。
简单推一下公式 x＝E/G
#include<bits/stdc++.h>
using namespace std;
using ll= long long;
int main()
{
double w,p,v,s{0};
cin>>w>>p;
v=2*1000*100/w;
while(v>0.000001){
s+=v/9.8;
v*=(100-p)*0.01;
}
printf("%.3f",s);
}
学习高级语法,c++中,struct≈calss,同样可以直接定义函数;
标签：std,21,people,int,28,long,2024,using,save From： https://www.cnblogs.com/manjuan/p/17992749