13230668653

13230668653
2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


13230668653
2个月前

#include<cstdio>
#include<iostream>
using namespace std;
const int N = 50010;
int p[N],d[N];
int find(int x){
if(x!=p[x]){
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main(){
int n,k,res = 0;
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;i++) p[i] = i;
while(k--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
int px = find(b),py = find(c);
if(b>n||c>n)  res++;
else if(a==1){
if(px==py&&(d[b]-d[c])%3!=0) res++;
else if(px!=py){
p[px] = py;
d[px] = d[c] - d[b];
}
}else{
if(px==py&&(d[b]-d[c]-1)%3!=0) res++;
else if(px!=py){
p[px] = py;
d[px] = d[c]+1-d[b];
}
}
}
cout<<res<<endl;
}


13230668653
2个月前

YXC的代码是不是麻烦了，二分查找，小于等于x最大的数。这样就不用把查询的坐标也离散化了。加一个哨兵防止，l小于离散化中最小的数导致二分查找不到。

#### C++ 代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
pair<int,int> a[N],b[N];

int request(pair<int,int> *a,int l,int r,int x){
while(l<r){
int mid = (l+r+1)/2;
if(a[mid].first>x)r = mid - 1;
else l = mid;
}
return a[l].second;
}

int main(){
int n,m,k;
cin>>n>>m;
for(int i = 1;i <= n;i++) scanf("%d%d",&a[i].first,&a[i].second);
sort(a+1,a+1+n);
for(int i = 1,j = 0;i<=n;i++){
if(i==1||a[i].first!=a[i-1].first)
b[++j] = a[i];
else b[j].second+=a[i].second;
k = j;
}
b[0].first = -1e9-1;
for(int i = 1;i <= k;i++) b[i].second+=b[i-1].second;
while(m--){
int l,r;
cin>>l>>r;
cout<<request(b,0,k,r) - request(b,0,k,l-1)<<endl;
}

}


13230668653
3个月前
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

void mul(int f[], int d[][2]) {
int cpy[2] = { 0 };
for (int i = 0; i < 2; i++) {
for (int k = 0; k < 2; k++) {
cpy[i] = (f[k] * d[k][i] + cpy[i]) % 10000;
}
}
for(int i = 0;i < 2;i++) f[i] = cpy[i];
}

void mulself(int d[][2]) {
int cpy[2][2] = { 0 };
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
cpy[i][j] = (cpy[i][j] + d[i][k] * d[k][j]) % 10000;
}
}
}
for(int i = 0;i < 4;i++) d[i/2][i%2] = cpy[i/2][i%2];
}

int main() {
int k;
while (scanf("%d", &k)&&k!=-1) {
int s[2] = { 0,1 };
int d[2][2] = { {0,1} ,{1,1} };
if (k == -1) return 0;
for (; k; k >>= 1) {
if (k & 1) mul(s, d);
mulself(d);
/*for(int i = 0;i < 4;i++) cout<<d[i/2][i%2]<<" ";
cout<<endl;
for(int i = 0;i < 2;i++) cout<<s[i]<<" ";
cout<<endl;*/
}
cout << s[0] << endl;
}
return 0;
}


13230668653
3个月前
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int L = 210,N = 1010;
int g[L][L],q[N],f[N][L][L];
int l,n;
int main(){
cin>>l>>n;
for(int i = 1;i <= l;i++)
for(int j = 1;j <= l;j++)
cin>>g[i][j];
for(int i = 1;i <= n;i++) cin>>q[i];
q[0] = 3;
memset(f,0x3f,sizeof f);
f[0][1][2] = 0;
for(int i = 0;i < n;i++){
for(int x = 1;x <= l;x++){
for(int y = 1;y <= l;y++){
int z = q[i],v = f[i][x][y],u = q[i+1];
if(x==y||x==z||y==z) continue;
f[i+1][x][y] = min(f[i+1][x][y],v+g[z][u]);
f[i+1][z][y] = min(f[i+1][z][y],v+g[x][u]);
f[i+1][x][z] = min(f[i+1][x][z],v+g[y][u]);
}
}
}
int ans = 0x3f3f3f3f;
for(int x = 1;x <= l;x++)
for(int y = 1;y <= l;y++){
int z = q[n];
if(x==y||x==z||y==z) continue;
ans = min(f[n][x][y],ans);
}

cout<<ans<<endl;
}


13230668653
3个月前
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2010;
int a[N],b[N],n,k = 1,f[N][N];//k代表目前有k-1个内容

int calc(){
sort(b+1,b+1+n);
for(int i = 1;i <= n;i++){
int maxv = 0x3fffffff;
for(int j = 1;j <= n;j++){
maxv = min(maxv,f[i-1][j]);
f[i][j] = maxv+abs(b[j]-a[i]);
//cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
}
}
int ans = 0x3fffffff;
for(int i = 1;i <= n;i++){
ans = min(ans,f[n][i]);
}
return ans;
}

int main(){
cin>>n;
for(int i = 1;i <= n;i++){
cin>>a[i];
b[i] = a[i];
}
int c = calc();
reverse(a+1,a+1+n);
int d = calc();
cout<<min(c,d)<<endl;
}


13230668653
3个月前
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
char str[3][30];
int path[30],q[30],n;//存储每个位置填的数，存储依次枚举的位置
bool st[30];

bool check(){
for(int i = n-1,t = 0;i>=0;i--){
int a = path[str[0][i] - 'A'],b = path[str[1][i] - 'A'],c = path[str[2][i] - 'A'];
if(a!=-1&&b!=-1&&c!=-1){
if(t==-1){
if((a+b)%n!=c&&(a+b+1)%n!=c) return false;
if(i==0&&a+b>=n) return false;
}else{
if((a+b+t)%n!=c) return false;
if(i==0&&a+b>=n) return false;
t = (a+b+t)/n;
}
}
else t = -1;
}
return true;
}

bool dfs(int u){
if(u==n) return true;
for(int i = n-1;i >= 0;i--){
if(st[i]==false){
path[q[u]] = i;
st[i] = true;
if(check()&&dfs(u+1)) return true;
st[i] = false;
path[q[u]] = -1;
}
}
return false;
}

int main(){
cin>>n;
for(int i = 0;i < 3;i++) cin>>str[i];

for(int i = n-1,k = 0;i >= 0;i--){
for(int j = 0;j < 3;j++){
int a = str[j][i] - 'A';
if(st[a]==false){
q[k++] = a;
st[a] = true;
}
}
}
memset(st,false,sizeof st);
memset(path,-1,sizeof path);
dfs(0);
for(int i = 0;i < n;i++) cout<<path[i]<<" ";
cout<<endl;
}


13230668653
3个月前
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 3010;
long long  a[N],b[N];
int f[N][N];
int main(){
int n;
scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
for(int i = 1;i <= n;i++) scanf("%lld",&b[i]);
a[0] = b[0] = -1e15;
for(int i = 1;i <= n;i++){
int v = 0;
for(int j = 1;j <= n;j++){
if(a[i]!=b[j]) f[i][j] = f[i-1][j];
else f[i][j] = v + 1;
if(b[j]<a[i]) v = max(v,f[i-1][j]);
}
}
int ans = 0;
for(int i = 1;i <= n;i++) ans = max(ans,f[n][i]);
cout<<ans<<endl;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


13230668653
3个月前
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int f[32][16][12][10][8];
int N[5];
int main(){
int k;
while(cin>>k&&k!=0){
memset(N,0,sizeof(N));
for(int i = 0;i < k;i++) cin>>N[i];
memset(f,0,sizeof(f));
f[0][0][0][0][0] = 1;
for(int a5 = 0;a5<=N[4];a5++){
for(int a4 = 0;a4<=N[3];a4++){
for(int a3 = 0;a3<=N[2];a3++){
for(int a2 = 0;a2<=N[1];a2++){
for(int a1 = 0;a1<=N[0];a1++){
if(a1<N[0]) f[a1+1][a2][a3][a4][a5] += f[a1][a2][a3][a4][a5];
if(a2<N[1]&&a2<a1) f[a1][a2+1][a3][a4][a5] += f[a1][a2][a3][a4][a5];
if(a3<N[2]&&a3<a2) f[a1][a2][a3+1][a4][a5] += f[a1][a2][a3][a4][a5];
if(a4<N[3]&&a4<a3) f[a1][a2][a3][a4+1][a5] += f[a1][a2][a3][a4][a5];
if(a5<N[4]&&a5<a4) f[a1][a2][a3][a4][a5+1] += f[a1][a2][a3][a4][a5];
}
}
}
}
}
cout<<f[N[0]][N[1]][N[2]][N[3]][N[4]]<<endl;;
}

}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


13230668653
3个月前
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1<<9;
int logone[N],ones[N],num[9][9],row[9],col[9],cell[3][3],ans = -1;
int sour[10][10];
bool st[10][10];
inline int lowbit(int x){
return x&(-x);
}
inline int pos(int x,int y){
return (10 - max(abs(x-4),abs(y-4)));
}

inline int get(int x,int y){
return row[x]&col[y]&cell[x/3][y/3];
}
void dfs(int cnt,int grate){
if(cnt==0){
ans = max(ans,grate);
return ;
}
int minnum = 10,x = 0 ,y = 0,f = 0;
for(int i = 0;i < 9;i++){
for(int j = 0;j < 9;j++){
if(st[i][j]==false){
int u = ones[row[i]&col[j]&cell[i/3][j/3]];
//f+=logone[u]*(10 - max(abs(x-4),abs(y-4)));
if(u<minnum) minnum = u,x = i,y = j;
}
}
}
//if(f+grate<=grate) return ;
for(int j = get(x,y);j;j-=lowbit(j)){
int k = lowbit(j);
row[x]-=k;
col[y]-=k;
cell[x/3][y/3]-=k;
st[x][y] = true;
dfs(cnt-1,grate + pos(x,y)*(logone[k]+1));
st[x][y] = false;
row[x]+=k;
col[y]+=k;
cell[x/3][y/3]+=k;
}
}

int main(){
int cnt = 0,grate = 0;
for(int i = 0;i < 9;i++){
for(int j = 1<<i;j< 1<<(i+1);j++)
logone[j] = i;//通过这个数组得到每个数的最高位，最优化剪枝
}
for(int i = 0;i < (1<<9);i++)
for(int j = i;j;j-=lowbit(j))
ones[i]++;
for(int i = 0;i < 9;i++) row[i] = col[i] = cell[i/3][i%3] = (1<<9)-1;
for(int i = 0;i < 9;i++){
for(int j = 0;j < 9;j++){
cin>>num[i][j];
if(num[i][j]!=0){
st[i][j]=true;
grate+=num[i][j]*pos(i,j);
row[i]-=1<<(num[i][j]-1);
col[j]-=1<<(num[i][j]-1);
cell[i/3][j/3] -= 1<<(num[i][j]-1);
}
else cnt++;
}
}
dfs(cnt,grate);
cout<<ans<<endl;

}