A CodeForces 1238A Prime Subtraction
水题，除了差1都行。
#include<stdio.h>
#include<set>
#include<iostream>
#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
const ll mod = 998244353;
const int N = 1e4 + 10;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll T,x,y;
int main(){
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&x,&y);
if(x-y==1){
printf("NO
");
}
else{
printf("YES
");
}
}
return 0;
}
B CodeForces 1238B Kill 'Em All
排序去重，从右向左炸。
#include<stdio.h>
#include<set>
#include<iostream>
#include<algorithm>
#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
const ll mod = 998244353;
const int N = 1e4 + 10;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll T,n,r;
ll a[100020];
ll cnt=0;
int main(){
scanf("%lld",&T);
while(T--){
cnt=0;
scanf("%lld%lld",&n,&r);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
sort(a+1,a+1+n);
n=unique(a+1,a+1+n)-(a+1);
for(int i=n;i>=1;i--){
if(a[i]-cnt*r<=0){
break;
}
cnt++;
}
printf("%lld
",cnt);
}
return 0;
}
C CodeForces 1238C Standard Free2play
比赛想成dp了，还没补。
D CodeForces 540C Ice Cave
染色，分类讨论。
#include<stdio.h>
#include<set>
#include<iostream>
#include<algorithm>
#include<cstring>
#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
const ll mod = 1000000007;
const int N = 1e4 + 10;
int f[5][5]={{0,1},{0,-1},{1,0},{-1,0}};
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int INF = 1e8;
using namespace std;
int n,m;
int a[520][520];
string s;
int sx,sy,tx,ty,cnt=0;
void dfs(int cx,int cy){
a[cx][cy]=cnt;
for(int i=0;i<4;i++){
int xx=cx+f[i][0],yy=cy+f[i][1];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]==0){
dfs(xx,yy);
}
}
}
int main() {
io_opt;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s;
for(int j=0;j<s.size();j++){
if(s[j]=='X'){
a[i][j+1]=-1;
}
else{
a[i][j+1]=0;
}
}
}
cin>>sx>>sy>>tx>>ty;
if(sx==tx&&sy==ty){
for(int i=0;i<4;i++){
int xx=sx+f[i][0],yy=sy+f[i][1];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]==0){
cout<<"YES
";
return 0;
}
}
cout<<"NO
";
return 0;
}
int k=0;
if(a[tx][ty]==-1){
k=1;
}
a[sx][sy]=a[tx][ty]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==0){
cnt++;
dfs(i,j);
}
}
}
if(a[sx][sy]!=a[tx][ty]){
cout<<"NO
";
}
else{
if(k==0){
int tmp=0;
for(int i=0;i<4;i++){
int xx=tx+f[i][0],yy=ty+f[i][1];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]!=-1){
tmp++;
}
}
if(tmp>1){
cout<<"YES
";
}
else{
cout<<"NO
";
}
}
else{
cout<<"YES
";
}
}
return 0;
}
E CodeForces 545C Woodcutters
宽度为3的dp。
#include<stdio.h>
#include<set>
#include<iostream>
#include<algorithm>
#include<cstring>
#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
const ll mod = 1000000007;
const int N = 1e4 + 10;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int INF = 1e8;
using namespace std;
int n,a[100020];
int f[100020][4];
struct E{
int x,h;
}e[100020];
int main() {
io_opt;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&e[i].x,&e[i].h);
}
e[0].x=-2e9-10;
e[0].h=0;
e[n+1].x=2e9+10;
e[n+1].h=0;
for(int i=1;i<=n;i++){
f[i][0]=max(f[i-1][0],max(f[i-1][1],f[i-1][2]));
if(e[i].x-e[i].h>e[i-1].x+e[i-1].h){
f[i][1]=f[i][0]+1;
}
else if(e[i].x-e[i].h>e[i-1].x){
f[i][1]=max(f[i][2],max(f[i-1][0],f[i-1][1])+1);
}
else{
f[i][1]=f[i][0];
}
if(e[i].x+e[i].h<e[i+1].x){
f[i][2]=f[i][0]+1;
}
}
printf("%d
",max(f[n][0],max(f[n][1],f[n][2])));
return 0;
}
F CodeForces 1230A Dawid and Bags of Candies
之前组队打过，当时没注意1，3个也行，wa了好久。
#include<iostream>
using namespace std;
int a[10];
int sum, tot;
int main() {
for (int i = 0; i < 4; i++) {
cin >> a[i];
sum += a[i];
}
if (a[0] + a[1] == a[2] + a[3] || a[0] + a[2] == a[1] + a[3] || a[0] + a[3] == a[1] + a[2] ||
a[0] == a[1] + a[2] + a[3] || a[1] == a[0] + a[2] + a[3] || a[2] == a[0] + a[1] + a[3] ||
a[3] == a[0] + a[1] + a[2]) {
cout << "YES
";
} else {
cout << "NO
";
}
return 0;
}
G CodeForces 1230B Ania and Minimizing
贪心。
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#include<stack>
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mem(arr) memset(arr,0,sizeof(arr))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
const ll mod = 998244353;
using namespace std;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
inline ll read() {
ll data = 0;
char ch = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = getchar();
return data;
}
const int N = 5e5 + 10;
ll n, k;
string s;
int main() {
cin >> n >> k;
cin >> s;
if (k == 0) cout << s << endl;
else if (n == 1) cout << '0'<<endl;
else {
if (s[0] != '1') s[0] = '1', --k;
for (int i = 1; i < s.size(); i++) {
if (k == 0) break;
if (s[i] != '0') {
s[i] = '0';
--k;
}
}
cout << s << endl;
}
return 0;
}
H CodeForces 1228B Filling the Grid
一开始以为那个是数量...
如果匹配，剩下的2的个数幂。
#include<stdio.h>
#include<set>
#include<iostream>
#include<algorithm>
#include<cstring>
#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
const ll mod = 1000000007;
const int N = 1e4 + 10;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int INF = 1e8;
using namespace std;
int h,w;
int a[1020][1020];
int x,cnt;
ll lowspeed(ll a,ll b,ll p){
ll cur=a,ans=0;
while(b){
if(b&1) ans=(ans+cur)%p;
cur=(cur+cur)%p;
b>>=1;
}
return ans%p;
}
ll speed(ll a,ll b,ll p){
ll cur=a,ans=1;
while(b){
if(b&1) ans=lowspeed(ans,cur,p)%p;
cur=lowspeed(cur,cur,p)%p;
b>>=1;
}
return ans%p;
}
int main() {
memset(a,-1,sizeof(a));
scanf("%d%d",&h,&w);
for(int i=1;i<=h;i++){
scanf("%d",&x);
for(int j=1;j<=x;j++){
a[i][j]=1;
}
a[i][x+1]=0;
}
for(int i=1;i<=w;i++){
scanf("%d",&x);
for(int j=1;j<=x;j++){
if(a[j][i]==0){
printf("0
");
return 0;
}
a[j][i]=1;
}
if(a[x+1][i]==1){
printf("0
");
return 0;
}
a[x+1][i]=0;
}
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(a[i][j]==-1) cnt++;
}
}
ll ans=speed(2,cnt,mod);
printf("%lld
",ans);
return 0;
}
I CodeForces 1228C Primes and Multiplication
题不难，就是麻烦，算就行。
#include<stdio.h>
#include<set>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
const ll mod = 1e9+7;
const int N = 1e4 + 10;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int INF = 1e8;
using namespace std;
ll lowspeed(ll a,ll b,ll p){
ll cur=a,ans=0;
while(b){
if(b&1) ans=(ans+cur)%p;
cur=(cur+cur)%p;
b>>=1;
}
return ans%p;
}
ll speed(ll a,ll b,ll p){
ll cur=a,ans=1;
while(b){
if(b&1) ans=lowspeed(ans,cur,p)%p;
cur=lowspeed(cur,cur,p)%p;
b>>=1;
}
return ans%p;
}
const int MAXN=4e4;
bool ipr[MAXN+20];
int cnt,pri[MAXN/5];
void prime(){//∞£ Ω…∏∑®
int N=sqrt(MAXN)+0.5,mul;
memset(ipr,true,sizeof(ipr));
ipr[1]=false;
for(int i=2;i<=N;i++){
if(ipr[i]==true){
i==2?mul=1:mul=2;
for(int j=i*i;j<=MAXN;j+=i*mul){
ipr[j]=false;
}
}
}
for(int i=2;i<=MAXN;i++){
if(ipr[i]==true){
pri[++cnt]=i;
}
}
}
ll x,n,ans=1;
int inx[40020],ct=0;
int main() {
prime();
io_opt;
cin>>x>>n;
for(int i=1;i<=cnt&&x!=1;i++){
if(x%pri[i]==0){
inx[++ct]=pri[i];
}
while(x%pri[i]==0){
x/=pri[i];
}
}
if(x!=1){
inx[++ct]=x;
}
ll tmp;
for(int i=1;i<=ct;i++){
tmp=n;
while(tmp){
tmp/=inx[i];
ans=(ans*speed(inx[i],tmp,mod))%mod;
}
}
cout<<ans<<endl;
return 0;
}
J CodeForces 1210B Marcin and Training Camp
反向拓扑，用链表mle，用short的邻接矩阵存的。后来才知道有简单结论。
#include<stdio.h>
#include<set>
#include<iostream>
#include<algorithm>
#include<cstring>
#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
const ll mod = 1000000007;
const int N = 1e4 + 10;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int INF = 1e8;
using namespace std;
int ag[7020];
short ae[7020][7020];
int cnt=0;
int val[7020];
ll ski[7020];
int n;
ll ans=0;
bool f[7020];
int du[7020];
int s;
void dfs(int cur){
//printf("%d
",cur);
s--;
f[cur]=true;
ans-=val[cur];
for(int i=1;i<=n;i++){
if(ae[cur][i]){
du[i]--;
}
}
for(int i=1;i<=n;i++){
if(!f[i]&&du[i]==s){
dfs(i);
}
}
}
int main() {
io_opt;
cin>>n;
s=n-1;
for(int i=1;i<=n;i++){
cin>>ski[i];
}
for(int i=1;i<=n;i++){
cin>>val[i];
ans+=val[i];
}
for(short i=1;i<=n;i++){
for(short j=i+1;j<=n;j++){
ll tmp=ski[i]^ski[j];
if(tmp&ski[i]){
//e[++cnt]=(E){i,j,g[i]};g[i]=cnt;
//ae[++cnt]=(E){i,ag[j]};ag[j]=cnt;
ae[j][i]=1;
//printf("%d %d
",i,j);
du[i]++;
}
if(tmp&ski[j]){
//e[++cnt]=(E){j,i,g[j]};g[j]=cnt;
//ae[++cnt]=(E){j,ag[i]};ag[i]=cnt;
ae[i][j]=1;
//printf("%d %d
",j,i);
du[j]++;
}
}
}
//cout<<"???"<<endl;
//cout<<"???"<<endl;
//cout<<"!!!"<<du[5]<<endl;
bool fg;
do{
fg=false;
for(int i=1;i<=n;i++){
//cout<<"du"<<du[i]<<endl;
if(du[i]==s&&!f[i]){
fg=true;
dfs(i);
}
}
}while(fg);
//cout<<s<<endl;
cout<<ans<<endl;
return 0;
}
K CodeForces 1157D N Problems During K Days
L CodeForces 1157E Minimum Array
multiset，找不到就找后面一个，后面没了就找第一个。
#include<stdio.h>
#include<set>
#include<iostream>
#include<algorithm>
#include<cstring>
#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
const ll mod = 1000000007;
const int N = 1e4 + 10;
int f[5][5]={{0,1},{0,-1},{1,0},{-1,0}};
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int INF = 1e8;
using namespace std;
multiset<int>q;
int n;
int a[200020];
int b[200020];
int x;
int main() {
io_opt;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int j=1;j<=n;j++){
cin>>x;
q.insert(x);
}
for(int i=1;i<=n;i++){
int tmp=n-a[i];
auto cur=q.lower_bound(tmp);
if(cur!=q.end()&&*cur==tmp){
cout<<"0 ";
q.erase(cur);
}
else{
if(cur==q.end()){
cout<<(a[i]+*q.begin())%n<<' ';
q.erase(q.begin());
}
else{
cout<<(a[i]+*cur)%n<<' ';
q.erase(cur);
}
}
}
return 0;
}